n个字串
m个母串
字串在母串中出现几次
#include<stdio.h> #include<algorithm> #include<string.h> #include<queue> #include<vector> using namespace std; #define MAXN 130 //AC自动机 class node { public: int index; node * fail; node * next[MAXN]; node() { index=0; fail=0; memset(next,0,sizeof(next)); } }; node *root; //插入操作 来看自动机的肯定看过tire 没看过就别看了 void Insert(char *s,int id) { node *p=root; while(*s) { int ind=*s-' '; if(!p->next[ind]) p->next[ind]=new node; p=p->next[ind]; s++; } p->index=id; } queue<node*>q1; void Build() { q1.push(root); root->fail=NULL;//根节点 while(!q1.empty()) { node *p=NULL; node *now=q1.front(); q1.pop(); for(int i=0;i<MAXN;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]); } } } } bool flag[550]; vector<int>z[1010]; char s1[10010]; void Ques(char *s1,int id) { node *p=root; memset(flag,0,sizeof(flag)); int ind,len=strlen(s1); for(int i=0;i<len;i++) { ind=s1[i]-' '; while(p->next[ind]==NULL&&p!=root)//存在的 p=p->fail; p=p->next[ind]; if(!p) p=root; node *now=p; while(now!=root&&!flag[now->index])//一个一个检验 这边是否有可以匹配的 子串 后缀相同 { if(now->index) { z[id].push_back(now->index); flag[now->index]=1; } now=now->fail; } if(z[id].size()>=3) break; } } int main() { int n; while(scanf("%d",&n)!=EOF) { getchar(); char s[210]; root=new node; for(int i=1;i<=n;i++) { scanf("%s",s); Insert(s,i); } Build(); int m; scanf("%d",&m); int ans=0; for(int i=1;i<=m;i++) { z[i].clear(); scanf("%s",s1); Ques(s1,i); if(z[i].size()>0) { sort(z[i].begin(),z[i].end()); ans++; } } for(int i=1;i<=m;i++) { if(z[i].size()) { printf("web %d:",i); for(int j=0;j<z[i].size();j++) printf(" %d",z[i][j]); printf(" "); } } printf("total: %d ",ans); } return 0; }