Fail树

0.引入

我们在写KMP的时候会求出来长度为$n$的字符串的前缀最长border的长度为$Next[n]$，接下来先介绍一个border

1. 定义：对于一字符串$S$，用$|S|$表示其长度，后面我们简化用$len_S$来表示，那么$S$串的一个Border一定是$S$串的一个前缀，并且他前缀和后缀都能够相互匹配。举个例子，比如说“BeckyBe”的一个border就是Be,一个字符串的border可能有多个，但在这里我们要求的是最长的border
2. 对于任意一个字符串$S$，一个Border的长度就对应一个Border（比如说上面的长度为2各border只能是“Be”），我们可以求出他所有border的长度分别为$ne[$$len_S$]，$ne[ne[$$len_S$$]$$]$ 以此类推直到为0。根据上面的结论，我们可以知道，对一个字符串S求解next数组之后，我们就知道了S所有前缀（包括S自身）的所有Border了。

1.Fail树

fail树就是把所有$next[i]$的节点指向$i$的有向边所构成的树，这课树，是自底部指向顶部，最终汇聚到一个$root$点。
例如一个字符串“aaaabbabbaa”，我们可以得到他的$next$数组如下

POS:1 2 3 4 5 6 7 8 9 10 11
S:  a a a a b b a b b a  a
Ne: 0 1 2 3 0 0 1 0 0 1  2 

我们画出他的fail树就是如下

结合前面Border的结论，在fail树上，一个结点x不断向上寻找祖先的过程，就是遍历字符串S[1,x]的所有Border长度的过程，又因为Border的长度和Border一一对应，所以fail树上就记录着字符串S所有前缀的Border。

根据前面所说，我们就能推出以下结论，S的两个前缀S[1,p]和S[1,q]的公共最长Border长度，就是$Lca(ne[p],ne[q])$

到这里你应该就能理解KMP在失配的情况下其实就是在回溯fail树。

模板失配树

代码如下

#include<iostream>
#include<cstring>
using namespace std;
const int MN=1e6+15,ML=20;
string s;
int m,fa[MN][40],dep[MN],pre[MN],n;
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=__lg(n)+1;i>=0;i--){
        if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];
    }
    if(x==y) return x;
    for(int i=__lg(n)+1;i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
int main(){
    cin>>s;
    n=s.length();
    s=" "+s;
    //cout<<"N:"<<n<<endl;
    for(int i=2,j=0;i<=n;i++){
        while(j&&s[i]!=s[j+1]){
            j=pre[j];
        }
        if(s[i]==s[j+1])j++;
        pre[i]=j;
        fa[i][0]=j;
        dep[i]=dep[j]+1;
    }
    for(int i=1;i<=n;i++){
        cout<<pre[i]<<" ";
    }
    cout<<endl;
    for(int k=1;k<=__lg(MN)+1;k++){
        for(int j=1;j<=n;j++){
            fa[j][k]=fa[fa[j][k-1]][k-1];
        }
    }
    cin>>m;
    for(int i=1;i<=n;i++){
        cout<<i<<" "<<fa[i][0]<<endl;
    }
    while (m--)
    {
        int p,q;
        cin>>p>>q;
        cout<<lca(fa[p][0],fa[q][0])<<endl;
    }
    
    return 0;
}