t
n个字串
1个母串
求出现几个字串
字串可能重复
#include<stdio.h> #include<algorithm> #include<string.h> #include<queue> using namespace std; class node { public: int mark; node *fail; node * next[30]; node() { mark=0; fail=0; memset(next,0,sizeof(next)); } }; bool flag[10010]; char s1[1000010]; node *root; queue<node *>q1; void Insert(char *s,int id) { node *p=root; while(*s) { int ind=*s-'a'; if(p->next[ind]==NULL) p->next[ind]=new node; p=p->next[ind]; s++; } p->mark++; } void Build() { q1.push(root); root->fail=0; while(!q1.empty()) { node *p=NULL; node *now=q1.front(); q1.pop(); for(int i=0;i<30;i++) { if(now->next[i]) { if(now==root) now->next[i]->fail=root; else { p=now->fail; while(p) { if(p->next[i]) { now->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL) now->next[i]->fail=root; } q1.push(now->next[i]); } } } } void dfs(node *p) { for(int i=0;i<30;i++) if(p->next[i]) dfs(p->next[i]); delete p; } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); root=new node; for(int i=1;i<=n;i++) { char s[55]; scanf("%s",s); Insert(s,i); } Build(); scanf("%s",s1); int ans=0; int len=strlen(s1); node *p=root; for(int i=0;i<len;i++) { int ind=s1[i]-'a'; while(p->next[ind]==NULL&&p!=root) p=p->fail; p=p->next[ind]; if(!p) p=root; node *now=p; while(now!=root&&now->mark!=-1) { ans+=now->mark; now->mark=-1; now=now->fail; } } printf("%d ",ans); dfs(root); } return 0; }