这篇文章上次修改于 227 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记14——KMP算法

简介

KMP算法是一个查找子串的算法，这种算法感觉在题目中都几乎不会出现了，但我们应当注意的是它的思想，算法思想大于算法本身。

问题

KMP算法输入两个字符串A和B，问B是否是A的一个子串，例如”ell”是“hello的子串”。并且返回匹配的位置。

暴力思路

暴力思路就是以A的每个下标位置开始，判断B的长度次数，复杂度易得O(mn)。

KMP思路 O(m + n)

如果让你去优化，肯定首先想到动态规划的基本思想，我算过的东西，能否利用起来，此处也就是，我之前比较了的数据，能否利用起来呢？

举一个例子：我在ABABABCAA 中寻找 ABABC

当我开始一一比对时，比对到第五个字母，A和C显然不匹配，下一步，理想上来说应该从第三个字符开始比对。

为什么跳到了第三个字符？

所以34个字符是AB，明显已经匹配了，所以我直接跳到了第三个字符进行比较。

KMP算法抓住了这一点，如何进行一个这样的跳跃比较呢？

重点在于，如何知道自己跳跃多少。看这里的ABAB，它要跳跃的是2，为什么，因为前两个字符和后两个字符一样，所以移动过去后，一样的字符还是一样的，而除去这个情况的前面情况也一定不匹配。

跳跃的时候，需要知道是子串的第几个字符不匹配，例如是子串的第i个字符不匹配，说明子串的前i - 1个字符是完全匹配的，对于这前i - 1个字符如果有首尾相同的情况，就把首移动到尾相同处的开头即可。

换个解释方法。

为了方便说明，设定我们在O串中查找S串：

我们换一种编码的形式来理解，已知S串为ABABC，O串为ABABABCAA。

检查到第五个字符的时候，我们知道S串的前面ABAB是匹配的，并且ABAB首尾相同都是AB，我们把AB编码成T，此时就变成S串为TTC，O串为TTA???，当TTC对应TTA不成立的时候，就往后一位，TTC下一步对照TA???查看是否对应，此时我们看似是只移动了一步，实际上我们跨越的T就是两个字符。

跳跃的步数

因此这个跳跃的步数是由查找的S串决定的，因为跳跃的是我们此处的T的长度，T又恰好是前面已经匹配那段进行的编码。我们的编码采用的是寻找前后缀相同的部分编码起来，所以T的长度就是前后缀相同部分的长度。

总结：跳跃的步数就是——前面已经匹配部分的前后缀最大相同长度。

代码实现

所以我们可以得到一个next数组（先不讨论求法）next[i]为前i个字符的前后缀相同最大长度。

int KMP(const string &s1, const string &s2, const vector<int> &next)
{
    int i = 0;
    int j = 0;
    int len1 = s1.size();
    int len2 = s2.size();
    while(i < len1 and j < len2){
        if(j == -1 or s1[i] == s2[j]){
            i++; j++;
        }else{
            j = next[j];
        }
    }
    if(j >= len2)
        return i - len2 + 1;
    else
        return -1;
}

复杂度分析，可见i不断递增，并且只走长度次，故复杂度为O(n).

还有一个细节：在解析中我们所说的跳跃，并没有很直接的体现出来，实际上的跳跃后，前几位因为是相同的，所以并不需要匹配。

如何预处理出next数组

next[i]为前i个字符的前后缀相同最大长度。例如：

A B A B C

0 0 1 2 0

推next数组的过程也是十分巧妙的，利用了同样DP的思想，使用之前计算的值。

例如ABACABAB

显然next[6] = 2

对于next[7],

如果S[2] = S[6] ，那么next[7] = next[6] + 1.

如果不相等，那么也就是 ABAC ≠ ABAB，上一个前缀是ABA

注意，我虽然4是不成立的，接下来我要寻找比4更小的长度，此时对于上一个相同点ABA，ABA的前后缀长度1相等，都为1，那么就有可能在前面的 (ABA) C 中取第一个 A，后面的 (ABA) ? 取第二个 A，检查后面的”?”是否等于ABAC中的B，此时就减少了一定量的计算，代码如下：

代码实现

vector<int> buildNext(const string &s1)
{
    vector<int> next(s1.size() + 1);
    next[0] = -1;
    next[1] = 0;
    int i = 1, prefixLen = 0;
    while (i < s1.size())
    {
        if (s1[prefixLen] == s1[i]){
            prefixLen++;
            next[i + 1] = prefixLen;
            i++;
        }
        else{
            if (prefixLen == 0){
                next[i + 1] = 0;
                i++;
            }else{
                prefixLen = next[prefixLen];
            }
        }
    }
    return next;
}

应用

在求两个字符串AB，A的前缀和B的后缀的最大公共部分，可以把两者合并在一起，然后求next数组，但是要注意长度问题，可以在A和B之间插入一个其他字符，也可以让答案取两者长度的最小值。

重复匹配

有的时候不仅仅是在查找子串，也要查找子串的个数，并且不允许重复，其实上只要在if(j >= len2)时，让i修改位置，并计数加一即可。

int KMP(const string &s1, const string &s2, const vector<int> &next)
{   
    int res = 0;

    int i = 0;
    int j = 0;
    int len1 = s1.size();
    int len2 = s2.size();
    while(i < len1){
        if(j == -1 or s1[i] == s2[j]){
            i++; j++;
        }else{
            j = next[j];
        }
        if(j >= len2){
            res ++;
            j = 0; // i已经递增过了
        }
    }
    return res;
}

Mai Icy