Keywords Search

#include<cstdio>#include<cstring>#include<queue>using namespace std;int n,t,tot=1,len;int v[500001],f[500001];char s[51],a[10000001];int trie[500001][27];queue<int>q;void insert(){    int root=1;    for(int i=0;i<len;i++)    {        int id=s[i]-‘a‘+1;        if(!trie[root][id])  trie[root][id]=++tot;        root=trie[root][id];    }    v[root]++;}void getfail(){    int root=1;    for(int i=1;i<=26;i++) trie[0][i]=1;    q.push(1);    while(!q.empty())    {        int now=q.front();        for(int i=1;i<=26;i++)        {            if(!trie[now][i]) continue;            q.push(trie[now][i]);            int j=f[now];            while(!trie[j][i]) j=f[j];            f[trie[now][i]]=trie[j][i];        }        q.pop();    }}void work(){    int root=1,ans=0;    for(int i=0;i<len;i++)    {        int id=a[i]-‘a‘+1;        while(!trie[root][id]) root=f[root];        root=trie[root][id];        if(v[root])         {            int j=root;            while(j)             {                ans+=v[j];                v[j]=0;                j=f[j];                   }        }    }    printf("%d\n",ans);}void pre(){    memset(v,0,sizeof(v));    memset(trie,0,sizeof(trie));    memset(f,0,sizeof(f));    tot=1;}int main(){    scanf("%d",&t);    while(t--)    {        pre();        scanf("%d",&n);        for(int i=1;i<=n;i++)         {            scanf("%s",s);            len=strlen(s);            insert();        }        getfail();        scanf("%s",a);        len=strlen(a);        work();    }}

#include<cstdio>#include<cstring>#include<queue>using namespace std;int n,t,tot=1,/*以1号节点为trie中根节点，不是0号*/len;int v[500001],f[500001];char s[51],a[10000001];int trie[500001][27];queue<int>q;void insert()//构造trie树 {    int root=1;    for(int i=0;i<len;i++)    {        int id=s[i]-‘a‘+1;        if(!trie[root][id])  trie[root][id]=++tot;        root=trie[root][id];    }    v[root]++;}void getfail()//bfs构造失配指针 {    int root=1;    for(int i=1;i<=26;i++) trie[0][i]=1;//0号节点（虚拟节点）的所有边都指向1      q.push(1);    while(!q.empty())    {        int now=q.front();        for(int i=1;i<=26;i++)//给now的子节点构造失配指针         {            if(!trie[now][i]) continue;            q.push(trie[now][i]);            int j=f[now];//父节点失配指针指向的点             while(!trie[j][i]) j=f[j];//从父节点失配指针指向的点开始，一直找，直至找到自己的失配指针应指向的点，//因为判断的是j有没有子节点，所以此句结束后，j=自己失配指针应该指向的点的父节点             f[trie[now][i]]=trie[j][i];//=左边：给now的子节点构造失配指针  =右边：j是失配指针应该指向的点的父节点，所以是trie[j][i]         }        q.pop();    }}void work(){    int root=1,ans=0;    for(int i=0;i<len;i++)    {        int id=a[i]-‘a‘+1;        while(!trie[root][id]) root=f[root];//root的子节点里没有点id，找root的失配指针//执行完此句后，root的子节点里有目标点id         root=trie[root][id];//转到目标点         if(v[root])         {            int j=root;            while(j) //例：模式串：she  he  要匹配的串：she //在找完路径s-h-e后，到达trie的底部，而此时还有he出现在了要匹配的串中，所以要沿着失配指针一直找//假设p的失配指针指向点u，那么满足性质：//把路径1——u构成的字符串称为前缀m，路径1——p构成字符串中所有后缀称为ni//满足m与ni是最大的             {                ans+=v[j];                v[j]=0;//防止对一个模式串重复匹配                 j=f[j];                   }        }    }    printf("%d\n",ans);}void pre(){    memset(v,0,sizeof(v));    memset(trie,0,sizeof(trie));    memset(f,0,sizeof(f));    tot=1;}int main(){    scanf("%d",&t);    while(t--)    {        pre();        scanf("%d",&n);        for(int i=1;i<=n;i++)         {            scanf("%s",s);            len=strlen(s);            insert();        }        getfail();        scanf("%s",a);        len=strlen(a);        work();    }}