KMP算法

原理

  KMP算法核心是ne数组，其定义是：从0（空串）到第i个模板串字符的子串为止，子串中前缀和后缀相等的最大长度，其中前缀和后缀不包括子串本身。

  举例来说，对于字符串ababab（按照下标从1开始存储，更为方便）：

• ne[0]总是0的原因是空串最长前缀也是0。
• ne[1] = 0的原因是长度为1的子串前缀如果不包括子串本身，也只有长度为0的空串，因此也是0。
• ne[2] = 0，(ab)abab此时子串ab的前缀没有和后缀相等的匹配。
• ne[3] = 1，(aba)bab的前缀可以看到下s[1] = a和s[3] = a相等。
• ne[4] = 2，(abab)ab的前缀可以看到{s[1], s[2]} = ab和{s[3], s[4]} = ab相等，这里由于只增加了一个字母，且当前最长前缀用到了长度为3子串时的最长前缀，所以最长前缀长度最多增加1，这一点很重要，是动态规划的思想。
• ne[5] = 3，(ababa)b，可以看到{s[1], s[2], s[3]} = aba和{s[3], s[4], s[5]} = aba相等。
• ne[6] = 4，（ababab), abab = abab。

  通过ne数组的定义，我们可以知道，当模板串和匹配串两个字符不匹配的时候，此时模板串的匹配位置就不必向后错一个位置继续从头匹配，而是从下一个前缀已经匹配完全的位置开始。

  这里通过将开始下标设置为1，之前定义的ne数组是前后缀的最大长度，正好也是当不匹配时，模板串应该移动到的下标位置。

  KMP算法求模板串ne数组的方法实际上是一种动态规划。每次使用了之前模板串中相同的长度，并且每次最长前缀最多+1，来计算下一次的最长前缀。当无法匹配的时候，正好通过定义j = ne[j]来跳到最大匹配位置继续。

模板

//n是模板串长度，m是匹配串长度
//p存储模板串，s存储匹配串

//产生ne数组的过程，模板串自己和自己匹配
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;
}

//在匹配串中匹配的过程
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)
    {
        //输出位置etc.
        j = ne[j];
    }
}

例题

AW.831 KMP字符串（简单）