hdu6138

201708 （ACM）字符串----AC自动机

• 通过这道题稍微理解了失败指针的含义

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=101010;
vi has[N];
int lev[N];
struct Trie {
    static const int N=101010 , M = 26;
    int ne[N][M] , fail[N] , fa[N] , rt , L;
    void ini() {
        fill_n(ne[fail[0] = N-1],M,0);
        L = 0;
        rt = newnode();
    }
    int newnode() {
        fill_n(ne[L],M,0);
        return L++;
    }
    void add(char *s,int id) {
        int p = rt;
        for(int i=0;s[i];++i) {
            int c = s[i] - 'a';
            if(!ne[p][c]) {
                ne[p][c] = newnode();
                fa[L-1]=p;
            }
            p = ne[p][c];
            has[id].pb(p);
            lev[p]=i+1;
        }
    }
    void Build() {
        vi v;v.pb(rt);
        rep(i,0,sz(v)) {
            int c = v[i];
            rep(i,0,M) ne[c][i] ?
                v.pb(ne[c][i]) , fail[ne[c][i]] = ne[fail[c]][i] :
                ne[c][i] = ne[fail[c]][i];
        }
    }
}tr;
int n,tim;
int vis[N];
char t[N];
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d",&n);
        ///init
        tr.ini();
        tim=0;
        rep(i,0,n+1) has[i].clear();
        memset(vis,0,sizeof(vis));
        ///read
        rep(i,0,n) {
            scanf("%s",t);
            tr.add(t,i);
        }
        ///solve
        tr.Build();
        int m;scanf("%d",&m);
        while(m--) {
            int u,v;scanf("%d%d",&u,&v);
            --u;--v;
            vi q;++tim;
            for(auto e : has[u]) {
                vis[e]=tim;
                q.pb(e);
            }
            rep(i,0,sz(q)) {
                int c=q[i];
                if(!c) continue;
                int e=tr.fail[c];
                if(vis[e]!=tim) {
                    vis[e]=tim;
                    q.pb(e);
                }
            }
            int ans=0;
            q.clear();++tim;
            for(auto e : has[v]) {
                if(vis[e]==tim-1) ans=max(ans,lev[e]);
                vis[e]=tim;
                q.pb(e);
            }
            rep(i,0,sz(q)) {
                int c=q[i];
                if(!c) continue;
                int e=tr.fail[c];
                if(vis[e]==tim-1) ans=max(ans,lev[e]);
                vis[e]=tim;
                q.pb(e);
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}