字典树也可以做。
#include<stdio.h> #include<string.h> #include<stdlib.h> #define maxn 1000010 struct ac_mation { ac_mation *fail;//失败指针 ac_mation *next[26];//26个字母 int flag;//标记是否为最后一个点 init(){//函数初始化 flag=0; fail=NULL; for(int i=0;i<26;i++) next[i]=NULL; } }*q[500010]; ac_mation *root; char s[maxn],str[60]; int n,head,tail; void insert(char *str) { int i,j,len=strlen(str); ac_mation *p=root,*qq; for(i=0;i<len;i++) { int id=str[i]-'a'; if(p->next[id]==NULL) { qq=new ac_mation; qq->init(); p->next[id]=qq; } p=p->next[id]; } p->flag++; } void getfail()//构建失败指针 { int i; q[tail++]=root; while(head!=tail)//bfs { ac_mation *p=q[head++]; ac_mation *temp=NULL; for(i=0;i<26;i++) { if(p->next[i]!=NULL) { if(p==root)//第一个元素的fail指针必须是root p->next[i]->fail=root; else { temp=p->fail;//失败指针 while(temp!=NULL)//如果找到了 { if(temp->next[i] != NULL)//找到 { p->next[i]->fail = temp->next[i]; break; } temp=temp->fail; } if(temp==NULL)//找不到 p->next[i]->fail=root; } q[tail++]=p->next[i]; } } } } void query(char *s) { int ans=0; int i,j,len=strlen(s); ac_mation *p=root,*temp; for(i=0;i<len;i++) { int id=s[i]-'a'; while(p->next[id]==NULL&&p!=root)//跳转到失败指针 p=p->fail; p=p->next[id]; if(p==NULL) p=root; temp=p; while(temp!=root&&temp->flag!=-1) { ans+=temp->flag; temp->flag=-1; temp=temp->fail; } } printf("%d ",ans); } void freeac_mation(ac_mation *root) { int i; for(i=0;i<26;i++) { if(root->next[i]) freeac_mation(root->next[i]); } free(root); } int main() { int i,t,j; scanf("%d",&t); while(t--) { head=tail=0; root=new ac_mation; root->init(); scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s",str); insert(str); } getfail(); scanf("%s",s); query(s); freeac_mation(root); } }