【黑马计划-1】KMP及扩展KMP

KMP

核心

玄学 fail$fail$ 数组
fail$fail$ 数组的含义即是某段字符串的最长公共前后缀。
具体来讲，设 T[1…j−1]=T[i−j…i−1](j⩽i)$T[1\dots j-1]=T[i-j\dots i-1](j⩽i)$ ，那么 fail[i]$fail[i]$ 为 j$j$ 的最大值。

那么这个 fail$fail$ 有什么用呢？见下图。

匹配时，设当前匹配到 S$S$ 的第 i$i$ 位， T$T$ 的第 j$j$ 位，即 S[i−j+1…i−1]$S[i-j+1\dots i-1]$ 与 T[1…j−1]$T[1\dots j-1]$ 已成功匹配。当 j$j$ 指针这一位发生失配，意味着 S[i]!=T[j]$S[i]!=T[j]$ ，这时根据 fail$fail$ 数组的定义，由于 T[1…fail[j]−1]=T[j−fail[j]…j−1]$T[1\dots fail[j]-1]=T[j-fail[j]\dots j-1]$ ，因此若将 j$j$ 指针指向 fail[j]$fail[j]$ ，我们可以直接跳过对 T[1…fail[j]−1]$T[1\dots fail[j]-1]$ 的匹配。

复杂度证明

设 n$n$ 为串 S$S$ 的长度， m$m$ 为串 T$T$ 的长度。
i$i$ 指针全程只增，这里的复杂度为 O(n)$O(n)$ ；
j$j$ 指针全程只有两种跳法： j→j+1$j\to j+1$ 或 j→fail[j]$j\to fail[j]$ 。
对于 j→j+1$j\to j+1$ 全程最多跳 n$n$ 次。
对于 j→fail[j]$j\to fail[j]$ ：
在 i$i$ 保持不变的情况下， j$j$ 跳至下界的极限次数一定不超过 j$j$ （根据 fail$fail$ 的定义）。因此设 f[j]$f[j]$ 表示 j$j$ 这个位置发生失配跳至下界的上限次数， g[j]$g[j]$ 为跳完 f[j]$f[j]$ 次之后 j$j$ 的位置。而 j$j$ 每跳一次， g[j]$g[j]$ 一定减小至少 1$1$ ， f[j]$f[j]$ 随之减小至少 1$1$ ，从而最终跳的次数上界为 U=max{f[j]}$U=max\{f[j]\}$ 。由 f$f$ 的定义我们知道， max{f[x]}=n$max\{f[x]\}=n$ ，故最终 j$j$ 跳的次数一定不超过 n$n$ 。
又由于要单独对串 T$T$ 单独求一次 fail$fail$ ，复杂度证明同上，为 O(m)$O(m)$ 。
综上，由于 i$i$ 全程迭代 n$n$ 次， j$j$ 全程迭代不超过 n$n$ 次，故时间复杂度为 O(n+m)$O(n+m)$ 。

扩展KMP

“扩展”

引入 ext$ext$ 数组， ext[i]$ext[i]$ 表示 S[i…n]$S[i\dots n]$ 与 T[1…m]$T[1\dots m]$ 的最长公共前缀（ n$n$ 为串 S$S$ 的长度， m$m$ 为串 T$T$ 的长度）。
考虑如何求 ext$ext$ 。

引入辅助工具

设当前需要计算 ext[i]$ext[i]$ 的值， p$p$ 为 ext[j]$ext[j]$ 最大时 j$j$ 的值 (1⩽j<i)$(1⩽j<i)$ ，
就有 S[p…p+ext[p]−1]=T[1…ext[p]]$S[p\dots p+ext[p]-1]=T[1\dots ext[p]]$，
于是 S[i…p]=T[ext[p]−p+i…ext[p]]$S[i\dots p]=T[ext[p]-p+i\dots ext[p]]$ 。
这时求 ext$ext$ 就有两种情况：
1、 i+fail[i]<p+ext[p]$i+fail[i]<p+ext[p]$
由于 S[i…p]=T[ext[p]−p+i…ext[p]]$S[i\dots p]=T[ext[p]-p+i\dots ext[p]]$ ，
又由 fail$fail$ 的定义知 S[i…i+fail[i−p+1]−1]=T[1…fail[i−p+1]]$S[i\dots i+fail[i-p+1]-1]=T[1\dots fail[i-p+1]]$ ， fail[i−p+1]$fail[i-p+1]$ 为最大匹配长度，故 ext[i]=fail[i−p+1]$ext[i]=fail[i-p+1]$ 。

2、 i+fail[i]≥p+ext[p]$i+fail[i]\ge p+ext[p]$
此处求法与 fail$fail$ 求法几乎一样，可参考 fail$fail$ 的求值。

复杂度证明：对于情况1，单次复杂度为 O(1)$O(1)$ ；对于情况2，总复杂度与KMP算法中一致，为 O(n+m)$O(n+m)$ 。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int LENGTH=1000000;
char S[LENGTH+2],T[LENGTH+2];

namespace KMP{
    int fail[LENGTH+2];
    int cnt[LENGTH+2],ext[LENGTH+2];
    void get_fail(char *t){
        int len=strlen(t+1);
        for(int i=2,j=0;i<=len;++i){
            while(j&&t[i]!=t[j+1])j=fail[j];
            if(t[i]==t[j+1])fail[i]=++j;
        }
    }
    void KMP(char *s,char *t){
        get_fail(t);
        int s_len=strlen(s+1),t_len=strlen(t+1);
        for(int i=1,j=0;i<=s_len;++i){
            while(j&&s[i]!=t[j+1])j=fail[j];
            if(s[i]==t[j+1]){
                cnt[i]=++j;
                if(j==t_len)j=fail[j];
            }
        }
    }
    void ex_KMP(char *s,char *t){
        get_fail(t);
        int s_len=strlen(s+1),t_len=strlen(t+1);
        int p=1;
        while(ext[1]<t_len&&s[ext[1]+1]==t[ext[1]+1])++ext[1];
        for(int i=2;i<=s_len;++i){
            if(i+fail[i-p+1]<p+ext[p])ext[i]=fail[i-p+1];
            else{
                int j=ext[p]+p-i;
                if(j<0)j=0;
                while(i+j<=s_len&&j<t_len&&s[i+j]==t[j+1])++j;
                ext[i]=j;
                p=i;
            }
        }
    }
}

int main(){
    scanf("%s%s",S+1,T+1);
    KMP::KMP(S,T);
    KMP::ex_KMP(S,T);
    int s_len=strlen(S+1),t_len=strlen(T+1);
    printf("Array of fail:\n\t");
    for(int i=1;i<=t_len;++i)printf("%d ",KMP::fail[i]);
    printf("\nMatching position:\n\t");
    for(int i=1;i<=s_len;++i)if(KMP::cnt[i]==t_len)printf("%d ",i-t_len+1);
    printf("\nArray of extend:\n\t");
    for(int i=1;i<=s_len;++i)printf("%d ",KMP::ext[i]);
}