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算法

上一篇:?【Java技术指南】「Guava Collections」实战使用相关Guava不一般的集合框架


下一篇:《玩转掌上生活——手机网上生活达人秘笈》一第1章 走进掌上生活