ac自动机裸题，但我还是写的trie图。

还有，访问过的点要打标记，不然会tle。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int T,n,tot;char s[60],st[1000050];struct Trie{    int ch[28];    int f,w,vis;}tr[500500];void init(){    for(int i=0;i<=tot;i++)    {        tr[i].f = tr[i].w = tr[i].vis = 0;        for(int j=1;j<=26;j++)            tr[i].ch[j] = 0;    }    tot=0;}void trie_pic(){    queue
         
          q;    for(int i=1;i<=26;i++)        if(tr[0].ch[i])            q.push(tr[0].ch[i]);    while(!q.empty())    {        int u = q.front();        q.pop();        for(int i=1;i<=26;i++)        {            int &v = tr[u].ch[i];            if(!v)            {                v = tr[tr[u].f].ch[i];                continue;            }            tr[v].f = tr[tr[u].f].ch[i];            q.push(v);        }    }}int main(){    scanf("%d",&T);    while(T--)    {        init();        tr[0].vis=1;        scanf("%d",&n);        for(int i=1;i<=n;i++)        {            scanf("%s",s+1);            int len = strlen(s+1);            int u = 0;            for(int j=1;j<=len;j++)            {                int c = s[j]-'a'+1;                if(!tr[u].ch[c])tr[u].ch[c] = ++tot;                u = tr[u].ch[c];            }            tr[u].w++;        }        trie_pic();        scanf("%s",st+1);        int u = 0,now,ans = 0,len = strlen(st+1);        for(int i=1;i<=len;i++)        {            int c = st[i]-'a'+1;            u = tr[u].ch[c];            now = u;            while(!tr[now].vis)            {                ans+=tr[now].w;                tr[now].w=0;                tr[now].vis=1;                now=tr[now].f;            }        }        printf("%d\n",ans);    }    return 0;}