hdu[2222]keywords search

3

#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=500001;
int n,root,dead[N],nxt[N][26],muff[N],tot,q[N<<1];
inline int create(){
    for(int i=0;i<26;i++)
        nxt[tot][i]=-1;
    dead[tot++]=0;
    return tot-1;
}
inline void ins(string tar){
    int now=root;
    for(int i=0;i<tar.size();i++){
        if(nxt[now][tar[i]-‘a‘]==-1)
            nxt[now][tar[i]-‘a‘]=create();
        now=nxt[now][tar[i]-‘a‘];
    }
    dead[now]++;
}
inline void build(){
    int hd=1,tl=0;
    for(int i=0;i<26;i++){
        if(nxt[root][i]==-1)
            nxt[root][i]=root;
        else
            muff[nxt[root][i]]=root,
            q[++tl]=nxt[root][i];
    }
    for(;hd<=tl;hd++){
        int now=q[hd];
        for(int i=0;i<26;i++){
            if(nxt[now][i]==-1)
                nxt[now][i]=nxt[muff[now]][i];
            else
                muff[nxt[now][i]]=nxt[muff[now]][i],
                q[++tl]=nxt[now][i];
        }
    }
}
inline int req(string tar){
    int res=0;
    for(int i=0,now=root;i<tar.size();i++){
        now=nxt[now][tar[i]-‘a‘];
        for(int tmp=now;tmp!=root;tmp=muff[tmp])
            res+=dead[tmp],
            dead[tmp]=0;
    }
    return res;
}
int main(){
    int T;
    string buf;
    ios::sync_with_stdio(false);
    cin>>T;
    for(;T;T--){
        memset(nxt,0,sizeof(nxt));
        memset(dead,0,sizeof(dead));
        memset(muff,0,sizeof(muff));
        tot=0;
        root=create();
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>buf,
            ins(buf);
        build();
        cin>>buf;
        cout<<req(buf)<<endl;
    }
    return 0;
}