KMP

我们谈一下 kmp 算法的思想与实现。

kmp 算法是一个在 O(n + m) 的时间复杂度下实现的字符串匹配算法。说道 O(n + m) 的字符串匹配，大家肯定很自然地想到 hash ，如果利用 hash 的话很轻易就实现了在 O(n + m) 的时间复杂度内匹配字符串了，但是，如果字符串本身很长或者字符比较多， hash 出来的值比较大， hash 便有些靠不住了，但是，我们不妨借助 hash 的思想来看 kmp 算法。

我们来看 hash 为什么可以在 O(n + m) 的时间复杂度内匹配字符串，对于下边一个例子：

abbbaaabcd

abc

我们需要在第一个字符串中找第二个字符串，对于 hash 的话我们先求出前三个字符的 hash 值，然后在一个一个往后推，也就是先求 abb 的 hash 值，然后向后走一个，求出 bbb 的 hash 值，直到有字符串的 hash 值为 abc 的 hash 值。不难发现，之所以 hash 快的原因是在匹配字符串失败后并没有完全放弃这个字符串，而是将有价值的字符串利用了起来，比如我们匹配 abb 的时候失败了，我们并没有直接从下一个字符从头开始匹配，而是保留了 abb 中 bb 的 hash 值，把一个 b 接在了后边。 kmp 的思想类似，我们在匹配失败后不要完全放弃这个匹配失败的子字符串，而是根据失败的信息得到某些信息，所以便快了。

考虑如何在不进行 hash 的情况下做到 hash 的保留信息，也就是说如何撮取匹配失败的信息并加以利用。

考虑我们在匹配失败之后直接放弃当前子字符串，跑到下一个不与之重叠的子字符串匹配的可行度，比如对于以上的例子，我们把 abc 对 abb 匹配失败后直接将 abc 与 baa 进行匹配，再次失败后直接匹配 abc 获得成功。这个想法对于上述例子来说似乎是可以的，但是我们只要将被匹配字符串中三个连续 a 中一个 a 去掉便不可以了，这样就匹配不到了。我们来分析具体原因。

abbbaabcd

xxxabc

其中 x 代表匹配过的字符(占位的而已)。

当我们匹配到这一步的时候，我们希望可以直接将 abc 和 abc 进行匹配，而不是跳过它。所以我们又得出了一个新的想法，在这个字符匹配失败后我们从失败位置的下一位开始匹配。也就是我们在匹配 baa 的时候在第一个 a 处不匹配了，我们从第一个 a 的下一个位置，也就是第二个 a 处重新开始匹配，就匹配到了 abc 。

经过了上边的教训，我们不得不思考这个方案的可行性。值得庆幸的是，这个方案对于大多数情况来说是可行的，但是我们还是找出了例外：

abaababaa

abab

对于这个例子，我们用我们刚才的想法就会导致不能匹配出结果。我们可以思考什么情况下我们上边的想法会出错。我们可以发现，当匹配字符串本身首尾有相同字串的情况下我们会出现错误，直接跳过了匹配那段重复子串的过程，然而这个时候是可能匹配上的。比如上述例子我们错过了与 abab 匹配。这貌似是个大错误，这也意味着我们必须要做些什么了。

所以说，我们可以处理出一个 next 数组， next[i] 代表匹配字符串的前 i + 1 个字符组成的子字符串中长度不为 i + 1 （i + 1 是为了与下表对应）的最长的前后缀相同的字串长度，比如 abab 来说 next[0] = 0, next[1] = 0, next[2] = 1, next[3] = 2 。这样的话，我们就可以在第匹配字符串 pp 个位置匹配失败时重新在匹配字符串的第 pp – 1 个位置继续与被匹配字符串的当前匹配字符进行匹配，我们假设被匹配字串当前匹配到了第 i 个位置，于是，我们的主要思想就有了：

如果 i 与 pp 位置成功匹配， i 和 pp 都加一，否则让 pp = next[pp – 1] 。如此匹配下去，就可以匹配到要匹配的字符串了。

那么问题来了，我们如何求出 next ，因为我们不可能花大把的时间在求 next 上。但是，我们发现，对于 next 数组，我们可以用 DP 的方法来将其求出。我们将匹配字符串命名为 str ，很显然地，若str[i] == str[next[i – 1]] ，那么 next[i] = next[i – 1] + 1 ，关键是不相等的情况，我们可以继续判断 str[i] 是否等于 str[next[next[i – 1]]] …… 如此循环下去，知道相等或为 0 。

所以说，我们可以显而易见地得出代码：

对于处理 next 数组的函数：

void init(){
    for(int i = 1; str2[i]; i++){
        int j = next[i – 1];
        while(j && str2[i] != str2[j]) j = next[j – 1];
        next[i] = j ? j + 1 : str2[0] == str2[i];
    }
}

对于处理 kmp 算法的函数(这个函数的功能是返回匹配被字符串里有多少个匹配字符串，str2为匹配字符串)：

int kmp(char *str){
    int pp = 0, ans = 0;
    for(int i = 0; str[i]; i++){
        while(pp && str[i] != str2[pp]) pp = next[pp – 1];
        if(str2[pp] == str[i]) pp++;
        if(!str2[pp]) ans++, pp = next[pp – 1];
    }
    return ans;
}

所以说，一个 O(n + m) 的字符串匹配算法就这么完事了。
百度上说处理 next 的时间复杂度为 O(m) ， kmp 时间复杂度为 O(n + m) ， 于是我们就相信了吧！