HDU 6138 Fleet of the Eternal Throne

题目大意：给出$n$ 个字符串，询问$m$ 次，每次询问$x$ 串和$y$ 串满足下面条件的最大子串长为多少。

• 该子串是串$x$ 和串$y$ 的连续公共子串
• 该字串是$n$ 个字符串的公共前缀

AC自动机

考虑到要求子串是$n$ 个字符串的公共前缀，可以建立AC自动机，并记录每个结点的深度（前缀长）。

然后跑一遍串$x$ ，标记经过的结点，表示既是$x$ 的子串又是$n$ 个字符串的公共前缀。

再跑一遍串$y$ ，如果当前结点已被标记，更新答案。

复杂度$O(n)$ 。

代码如下：

#include <iostream>
#include <string>
#include <queue>
using namespace std;
const int N=100005;
struct Trie{
    int Root,L;
    int Next[N][26],Fail[N],End[N],Dep[N],vis[N];
    int Newnode(){
        for(int i=0;i<26;++i)
            Next[L][i]=-1;
        End[L++]=0;
        return L-1;
    }
    void init(){
        L=0,Root=Newnode();
    }
    void Insert(string Buff){
        int len=Buff.length();
        int now=Root;
        for(int i=0;i<len;++i){
            int c=Buff[i]-'a';
            if(Next[now][c]==-1)
                Next[now][c]=Newnode();
            now=Next[now][c];
            Dep[now]=i+1;
        }
        End[now]++;
    }
    void Build(){
        queue<int>q;
        Fail[Root]=Root;
        for(int i=0;i<26;++i){
            if(Next[Root][i]==-1){
                Next[Root][i]=Root;
            }else{
                Fail[Next[Root][i]]=Root;
                q.push(Next[Root][i]);
            }
        }
        while(!q.empty()){
            int now=q.front();
            q.pop();
            for(int i=0;i<26;++i){
                if(Next[now][i]==-1){
                    Next[now][i]=Next[Fail[now]][i];
                }else{
                    Fail[Next[now][i]]=Next[Fail[now]][i];
                    q.push(Next[now][i]);
                }
            }
        }
    }
    int Query(string x,string y){
        int len=x.length();
        int now=Root;
        for(int i=0;i<len;++i){
            int c=x[i]-'a';
            now=Next[now][c];
            int temp=now;
            while(temp!=Root){
                vis[temp]=1;
                temp=Fail[temp];
            }
        }
        len=y.length();
        now=Root;
        int ans=0;
        for(int i=0;i<len;++i){
            int c=y[i]-'a';
            now=Next[now][c];
            int temp=now;
            while(temp!=Root){
                if(vis[temp])ans=max(ans,Dep[temp]);
                temp=Fail[temp];
            }
        }
        len=x.length();
        now=Root;
        for(int i=0;i<len;++i){
            int c=x[i]-'a';
            now=Next[now][c];
            int temp=now;
            while(temp!=Root){
                vis[temp]=0;
                temp=Fail[temp];
            }
        }
        return ans;
    }
}gao;
int T,n,m,x,y;
string s[N];
int main(void){
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        gao.init();
        cin>>n;
        for(int i=1;i<=n;++i){
            cin>>s[i];
            gao.Insert(s[i]);
        }
        gao.Build();
        cin>>m;
        while(m--){
            cin>>x>>y;
            cout<<gao.Query(s[x],s[y])<<"\n";
        }
    }
}