- #include
- #include
- #include
- using namespace std;
- intn,t,tot=1,/*以1号节点为trie中根节点,不是0号*/len;
- intv[500001],f[500001];
- chars[51],a[10000001];
- inttrie[500001][27];
- queue<int>q;
- voidinsert()//构造trie树
- {
- introot=1;
- for(inti=0;i)
- {
- intid=s[i]-'a'+1;
- if(!trie[root][id]) trie[root][id]=++tot;
- root=trie[root][id];
- }
- v[root]++;
- }
- voidgetfail()//bfs构造失配指针
- {
- introot=1;
- for(inti=1;i<=26;i++) trie[0][i]=1;//0号节点(虚拟节点)的所有边都指向1 q.push(1);
- while(!q.empty())
- {
- intnow=q.front();
- for(inti=1;i<=26;i++)//给now的子节点构造失配指针
- {
- if(!trie[now][i])continue;
- q.push(trie[now][i]);
- intj=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()
- {
- introot=1,ans=0;
- for(inti=0;i)
- {
- intid=a[i]-'a'+1;
- while(!trie[root][id]) root=f[root];
- //root的子节点里没有点id,找root的失配指针
- //执行完此句后,root的子节点里有目标点id root=trie[root][id];//转到目标点
- if(v[root])
- {
- intj=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(inti=1;i<=n;i++)
- {
- scanf("%s",s);
- len=strlen(s);
- insert();
- }
- getfail();
- scanf("%s",a);
- len=strlen(a);
- work();
- }
- }
来源: http://www.bubuko.com/infodetail-1965595.html