function cal_next($str){ $next[0] = -1;//next[0]初始化为-1 $i=0; $j = -1; $len=strlen($str); while($i<$len){ if($j===-1 || $str[$i]===$str[$j]){ $i++; $j++; $next[$i]=$j; }else{ $j=$next[$j]; } } return $next; }$str='ABCDABD';$next=cal_next($str); var_dump($next);function search($str,$search){ $next=cal_next($search); $i=0; $j=0; $lenStr=strlen($str); $lenSearch=strlen($search); while($i<$lenStr && $j<$lenSearch){ if($j===-1 || $str[$i]===$search[$j]){ //$i 主串的不后退,移动模式串。为什么没有$j===0,因为如果有$j++为1,下一步是判断$str[$i]===$search[1],跳过了$search[0] $i++; $j++; }else{ $j=$next[$j]; } } if($j===$lenSearch){ return $i-$j; } return -1; } var_dump(search($str,'ABD'));
[KMP算法(1):如何理解KMP](https://segmentfault.com/a/1190000008575379) [字符串匹配的KMP算法](http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html) [KMP算法最浅显理解](https://blog.csdn.net/starstar1992/article/details/54913261)
##
function cal_next($str){ $next[0] = -1;//next[0]初始化为-1 $i=0; $j = -1; $len=strlen($str); while($i<$len){ if($j===-1 || $str[$i]===$str[$j]){ $i++; $j++; $next[$i]=$j; }else{ $j=$next[$j]; } } return $next; }$str='ABCDABD';$next=cal_next($str); var_dump($next);function search($str,$search){ $next=cal_next($search); $i=0; $j=0; $lenStr=strlen($str); $lenSearch=strlen($search); while($i<$lenStr && $j<$lenSearch){ if($j===-1 || $str[$i]===$search[$j]){//$i 主串的不后退,移动模式串。为什么没有$j===0,因为如果有$j++为1,下一步是判断$str[$i]===$search[1],跳过了$search[0] $i++; $j++; }else{ $j=$next[$j]; } } if($j===$lenSearch){ return $i-$j; } return -1; } var_dump(search($str,'ABD'));
[KMP算法(1):如何理解KMP](https://segmentfault.com/a/1190000008575379) [字符串匹配的KMP算法](http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html) [KMP算法最浅显理解](https://blog.csdn.net/starstar1992/article/details/54913261)
PHP implements addition and subtraction verification code
php implements a simple calculator
PHP implements a simple Redis document lock And prevent concurrent repeated calls
The above is the detailed content of PHP implements KMP algorithm. For more information, please follow other related articles on the PHP Chinese website!