#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+50;
struct Node{
    int cnt;
    Node *fail;
    Node *Next[30];
}*que[maxn];
char s[maxn];
char keyword[55];
Node *root;
void init(Node *root){
    root->cnt=0;
    root->fail=NULL;
    for(int i=0;i<26;i++)
        root->Next[i]=NULL;
}
void Build_trie(char *keyword){
    Node *p,*q;
    int i,v;
    int len=strlen(keyword);
    for(i=0,p=root;i<len;i++){
        v=keyword[i]-'a';
        if(p->Next[v]==NULL){
            q=(struct Node *)malloc(sizeof(Node));
            init(q);
            p->Next[v]=q;
        }
        p=p->Next[v];
    }
    p->cnt++;
}
void Build_AC_automation(Node *root){
    int head=0,tail=0;
    que[head++]=root;
    while(head!=tail){
        Node *p=NULL;
        Node *temp=que[tail++];
        for(int i=0;i<26;i++){
            if(temp->Next[i]!=NULL){
                if(temp==root)
                    temp->Next[i]->fail=root;
                else{
                    p=temp->fail;
                    while(p!=NULL){
                        if(p->Next[i]!=NULL){
                            temp->Next[i]->fail=p->Next[i];
                            break;
                        }
                        p=p->fail;
                    }
                    if(p==NULL)
                        temp->Next[i]->fail=root;
                }
                que[head++]=temp->Next[i];
            }
        }
    }
}
int query(Node *root){
    int v,count=0;
    Node *p=root;
    int len=strlen(s);
    for(int i=0;i<len;i++){
        v=s[i]-'a';
        while(p->Next[v]==NULL && p!=root)
            p=p->fail;
        p=p->Next[v];
        if(p==NULL)
            p=root;
        Node *temp=p;
        while(temp!=root){
            if(temp->cnt>=0){
                count+=temp->cnt;
                temp->cnt=-1;
            }else
                break;
            temp=temp->fail;
        }
    }
    return count;
}
int main(){
    int T,n;scanf("%d",&T);
    while(T--){
        root=(struct Node *)malloc(sizeof(Node));
        init(root);
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%s",keyword);
            Build_trie(keyword);
        }
        Build_AC_automation(root);
        scanf("%s",s);
        printf("%d\n",query(root));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注