简介

KMP算法是在字符串中查找子串相关的算法,时间复杂度为O(n).

实现思路

中心思想:利用要查找的字符串的最长前后缀的信息跳过暴力查找算法那些重复匹配的内容.

1.使用辅助数组构建要查找的字符串中每个字符的最长前后缀数组.
2.匹配当前字符串与当前查找的字符串如果相等,二者匹配位置向后移.
3.如果不等且到了要查找字符的0位置那么当前字符匹配位置向后移.
4.如果不等且没到要查找字符的0位置,获取到当前,要查找字符串的最长前后缀的长度,要查找字符串的位置跳到最长前后缀的下一个位置接着匹配.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class KMP
{

    public function getNextArr($str)
    {
    
        $strLen = strlen($str);
        $len = 0;
        $lps[0] = -1;//起始位置是-1表示开头无最长前缀无最长后缀
        if ($strLen == 1) {   
            return $lps;
        }
        $lps[1] = 0;//0表示没有 最长前后缀
        if ($strLen == 2) {    
            return $lps;
        }
        $i = 2;
        while ($i < $strLen) {
            if ($str[$i - 1] == $str[$len]) {//当前字符的前一个位置与前缀位置相等
                $len++;
                $lps[$i] = $len;
                $i++;
            } else { //当前字符的前一个位置与前缀位置不等
                if ($len > 0) {
                    $len = $lps[$len]; //len是与i位置字符不一样字符的位置,取出len位置的前缀长度的位置找看是否一致.例:ababdababag ->-1001201234
                } else {
                    $lps[$i] = 0;//前缀为0
                    $i++;//下一个位置继续
                }
            }
        }
        return $lps;
    }

    /**
     * @param $str string
     * @param $findStr string
     * @return integer
     */
    public function findStr($str, $findStr)
    {

        $strLen = strlen($str);
        $findStrLen = strlen($findStr);
        if ($strLen < $findStrLen || $str === "" || $findStr === "") {
            return -1;
        }

        $lps = $this->getNextArr($findStr);//或取next数组

        $strIndex = 0;
        $findStrIndex = 0;

        while ($strIndex < $strLen && $findStrIndex < $findStrLen) {
            if ($str[$strIndex] == $findStr[$findStrIndex]) {//要查的字符与当前字符相等
                $strIndex++;
                $findStrIndex++;
            } else if ($lps[$findStrIndex] == -1){//要查的字符与当前字符不等,到了0位置 ,那么当前字符往下找
                $strIndex++;
            } else {//要查的字符与当前字符不等,没到0位置,查找最长前缀的下一个字符,在$findIndex之前我们的字符串都是相等的(此时$strIndex与$findStrIndex在$findStrLen下拥有共同的最长前后缀,且最长前缀与最长后缀相等),因此跳过该位置的最长前后缀的长度,在其下一个位置开始查找($lps[$findStrIndex])
            //也就是拿当前字符(当前字符串的最长后缀的下一个字符)与要查找字符串的最长前缀的下一个符进行比较.
                $findStrIndex = $lps[$findStrIndex];
            }
        }
        return $findStrIndex == $findStrLen ? $strIndex - $findStrIndex : -1; //如果找到了返回字符串的起始位置
    }
}

例子

要匹配的字符:

字符 a b a b g
lps数组 -1 0 0 1 2

当字符:ababdababg

匹配流程:

ababdababg
ababg

ababdababg
ababg
…

ababdababg
ababg

此时d,g不相等,匹配a,d跳过了ab字符,.

ababdababg
ababg

还是不相等所以调到了a.

ababdababag
ababg

还是不相等当前字符的位置向后移
ababdababag
ababg

…

ababdababg
ababg

匹配完成.