<?php
//构建部分匹配表
function part_match($goal,$match=null)
{
static $match;
$length = strlen($goal);
if($length < 2){
return;
}
for($i=0;$i<$length-1;$i++){
$left[] = substr($goal,0,$i+1);
$right[] = substr($goal,1+$i,$length-$i);
}
foreach(array_intersect($left,$right) as $v){
$len = strlen($v);
if($len > 1){
$match[$v[$len-1]] = $len;
continue;
}
$match[$v] = $len;
}
part_match(rtrim($goal,$goal[$length-1]));
return $match;
}
//执行kmp算法
function kmp($str,$goal)
{
$map = part_match($goal);
if(is_null($map) || empty($map)){
return null;
}
$glen = strlen($goal);
$result = [];
@[$a,$b] = [0,0];
while($b < $glen){
if($str[$a] == $goal[$b]){
$result[$b] = $str[$a];
$a++;
$b++;
continue;
}
if($b==0){
$a++;
continue;
}
//如果出现不匹配的情况，则a减一查找最后一次匹配顺序正确的数值
//将$goal当前的key值减去减去不需要在比较的部分得出$b要往回挪动的数值
$b = $b - ($b - $map[$str[$a-1]]);
}
return implode(‘‘,$result);
}
$str = "BBC ABCDAB ABCDABCDABDEBDQQQDQQQQDEFDQQQQQ";
$goal = "DQQQQDEFD";
$res = kmp($str,$goal);
var_dump($res);
