从头至尾彻底理解扩展KMP

从头到尾彻底理解扩展KMP

1. 扩展KMP问题：

求字符串S的所有后缀和字符串T的最长公共前缀。

扩展KMP可以用来解决很多字符串问题，如求一个字符串的最长回文子串和最长重复子串。

2. 拓展KMP的next[]数组怎么计算？

在解上面这个问题前我们要先解决一个类似的问题：
求字符串s的所有后缀和字符串s本身的最长公共前缀；
我们用 $next[]$ 数组保存这些值；

现在我们假设要求 $next[x]$ ，并且 $next[i]$ $(0<i<x)$ 的值都已经求出；
我们设 $p = k + next[k] - 1$ ， $k$ 是使 $p$ 最大的 $i$ $(0<i<x)$ 。

如图所示：
从头至尾彻底理解扩展KMP

现在整理一下问题：

已知： $s[k..p] = s[ 0 .. next[ k ]-1 ]$ ，求 $s[x .. n-1]$ 与 $s[0 .. n-1]$ 的最长公共前缀；

解：
由 $s[k .. p]$ = $s[ 0 .. next[ k ]-1 ]$ 得：
$s[x .. p]$ = $s[x-k .. next[ k ]-1 ]$ …………………….(1) 这个是显然的

并设 $L1=p-x+1$
因为 $x-k < x$ ，所以 $L2=next[x-k]$ 是已知的，得：
$s[0 .. L2-1] = s[x-k ... x-k+L2-1]$ …………………….(2)

通过等式(1)，(2)可以推出 $s[0 .. k1] = s[x .. k2]$

当 $L1 ≤ L2$ 时，如下图所示：
从头至尾彻底理解扩展KMP

表示 $s[0 .. L1-1] = s[x .. x+L1-1]$ ，但不能确定蓝色部分是否相等，所以需要继续比下去。

当 $L1 > L2$ 时，如下图所示：
从头至尾彻底理解扩展KMP

表示 $s[0 .. L2-1] = s[x .. x+L2-1]$ ，
而且因为 $L2 = next[x-k]$ ，使得 $s[L2] ≠ s[x+L2]$
所以 $next[x] = L2$

证明：
假设 $s[L2]=s[x+L2]$ ，
又因为 $s[x+L2]==s[x-k+L2]$ …………由(1)推出
所以 $s[L2]=s[x-k+L2]$ ，
所以 $next[x-k]=L2+1$ 与 $next[x-k]=L2$ 矛盾

求 $next[]$ 数组的代码如下：

void getNext(char *s, int next[]) {
    int lenS = strlen(s);

    next[0] = lenS;
    int p = 0;
    while (p+1 < lenS && s[p] == s[p+1]) p++;

    next[1] = p;
    int k = 1, L;
    for (int i = 2; i < lenS; i++) {
        p = k + next[k] - 1, L = next[i-k];
        if (i + L <= p)
            next[i] = L;
        else {
            int j = max(p-i+1, 0);
            while (i + j < lenS && s[i+j] == s[j]) j++;
            next[i] = j, k = i;
        } 
    }
}

3. 如何计算 $extend[]$ 数组的值

回到原来的问题
此时已经求出 $next[]$ ，我们用 $extend[]$ 保存字符串S的所有后缀和字符串T的最长公共前缀的值

求解 $extend[]$ 数组的方法和求解 $next[]$ 数组的方法类似，重复上面的过程：

假设要求 $extend[ x ]$ ，并且 $extend[ i ]$ $(0<i<x)$ 的值都已经求出；
我们设 $p = k + extend[k] - 1$ ， k是使p最大的 $i$ $(0<i<x)$ ；

如图所示：
从头至尾彻底理解扩展KMP

整理一下问题：

已知： $s[k..p] = T[ 0 .. extend[ k ]-1 ]$ ，求 $s[x .. n-1]$ 与 $T[0 .. m-1]$ 的最长公共前缀；

解：
由 $s[k .. p]$ = $T[ 0 .. extend[ k ]-1 ]$ 得：
$s[x .. p]$ = $T[x-k .. extend[ k ]-1 ]$ …………………….(1)

并设 $L1=p-x+1$
因为 $x-k < x$ ，所以 $L2=next[x-k]$ 是已知的，得：
$T[0 .. L2-1] = T[x-k ... x-k+L2-1]$ …………………….(2)

通过等式(1)，(2)可以推出 $T[0 .. k1] = s[x .. k2]$

当 $L1 ≤ L2$ 时，如下图所示：
从头至尾彻底理解扩展KMP

表示 $T[0 .. L1-1] = s[x .. x+L1-1]$ ，但不能确定蓝色部分是否相等，所以需要继续比下去。

当 $L1 > L2$ 时，如下图所示：
从头至尾彻底理解扩展KMP

表示 $T[0 .. L2-1] = s[x .. x+L2-1]$ ，
而且因为 $L2 = extend[x-k]$ ，使得 $T[L2] ≠ s[x+L2]$
所以 $extend[x] = L2$

证明：
假设 $T[L2]=s[x+L2]$ ，
又因为 $s[x+L2]=T[x-k+L2]$ …………由(1)推出
所以 $T[L2]==s[x-k+L2]$ ，
所以 $extend[x-k]=L2+1$ 与 $extend[x-k]=L2$ 矛盾

求 $extend[]$ 数组的代码如下：

void getExtend(char *s, char *T, int extend[], int next[]) {
    int lenS = strlen(s) ,lenT = strlen(T);
    getNext(s,next);

    int p = 0;
    while(p < lenS && s[p] == T[p]) p++;

    extend[0] = p;
    int k = 0, L;
    for(int i = 1; i < lenS; i++) {
        p = k + extend[k] - 1, L = next[i - k];
        if(i + L <= p)
            extend[i] = L;
        else {
            int j = max(p-i+1, 0);
            while (i + j < lenS && s[i + j] == T[j]) j++;
            extend[i] = j; k = i;
        } 
    }
}

4. 时间复杂度分析：

对于s串，计算next[]数组的时间是O(n)，计算extend[]数组的时间是O(m)的，总算法复杂度是O(n+m)；