PHP实现KMP算法

本文主要是介绍PHP实现KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

<?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);

这篇关于PHP实现KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！