KMP | Feeeiyuuu

“KMP” 是由三位科学家的名字首字母组成的——Knuth-Morris-Pratt。这个算法用来解决字符串匹配问题：在一个文本串中查找一个模式串有没有出现，以及出现的位置。

为什么需要kmp

最朴素的字符串匹配:拿模式串从主串的每一个位置开始逐个字符比较，一旦发现不匹配，就把模式串往后挪到主串的下一位，重新从头开始比较。

每次失配后，模式串指针都会回退，最坏的情况是时间复杂度是O(nm)（n是主串长度，m是模式串长度）。

思想

当字符串发生失配的时候，我们已经知道之前匹配成功的那部分字符是什么，这部分信息不会被浪费。利用这些已知信息，可以避免主串指针的回退。

我们先预处理模式串，构造一个ne[]数组：统计最长相等前后缀的长度。

ne[j]就表示模式串前j个字符构成的字串中，最长相等前后缀的长度。

举个例子，模式串p = ababc(下标从1开始)，预处理出来的ne数组是[0, 0, 1, 2, 0]。以ne[4] = 2为例：p前四个字符是“abab”，它最长的相等前后缀是“ab”（前缀“ab”和后缀“ab”),长度为2。 为什么失配时可以直接跳到ne[j]，而不用把指针退回起点？

假设主串s在匹配到"ababa..."时，前4个字符"abab"和模式串p完全匹配（此时j=4），但第5个字符失配了（s[5]='a'，而p[5]='c'）。这时候不需要把j退回0重新开始比较，因为：已经匹配上的这一段"abab"，本身就等于模式串p的前4个字符。p的前4个字符里，前缀"ab"和后缀"ab"是相等的。也就是说，s中刚刚失配位置往前数2个字符，其实已经天然地和模式串p的前2个字符对齐了。所以可以直接让j = ne[4] = 2，从p的第3个字符（j+1位置）继续和s的当前字符比较，不用退回起点重新扫。

复杂度

KMP总体是O(n + m)

构造ne数组是O(n)

for (int i = 2, j = 0; i <= n; i++) {
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j++;
    ne[i] = j;
}

不是O(n²)，这里用均摊分析。

主匹配过程是O(m)

 for (int i = 1, j = 0; i <= m; i++) {

    while (j && s[i] != p[j + 1])
      j = ne[j];

    if (s[i] == p[j + 1])
      j++;

    if (j == n) {
      printf("%d ", i - n);
      j = ne[j];
    }
}

均摊分析。

谢谢。