Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 42583 Accepted Submission(s): 9167
#include<iostream> #include<string.h> #include<string> #include<algorithm> #include<queue> #include<set> #define ll long long using namespace std; int tree[105000][128],vis[105000],fail[105000];//可能出现的字符是ASCII码,不是字母了 int t,n,cnt,id,root,num=0; string s,ss; set<int>m; void insert(int y)//建树 { root=0; for(int i=0;s[i];i++) { id=s[i];//-‘a‘,这里不能再减字符a,可能出现负数,直接默认转换成int型 if(tree[root][id]==0) tree[root][id]=++num; root=tree[root][id]; } vis[root]=y;//单词结尾标记 } void build()//构建失配指针 { queue<int>p; for(int i=0;i<128;i++) { if(tree[0][i])//将第二行所有出现过的字母的失配指针指向root节点0 { fail[tree[0][i]]=0; p.push(tree[0][i]); } } while(!p.empty()) { root=p.front(); p.pop(); for(int i=0;i<128;i++) { if(tree[root][i]==0)//没有建树,不存在这个字母 continue; p.push(tree[root][i]); int fa=fail[root];//fa是父亲节点 while(fa&&tree[fa][i]==0)//fa不为0,并且fa的子节点没有这个字母 fa=fail[fa];//继续判断fa的父亲节点的子节点有没有这个字母 fail[tree[root][i]]=tree[fa][i];//找到就构建失配指针 } } } int search(string ss)//查找 { root=0,cnt=0; for(int i=0;ss[i];i++) { id=ss[i]; while(root&&tree[root][id]==0)//失配转移 root=fail[root]; root=tree[root][id]; int temp=root; while(vis[temp]) { cnt=cnt+1; m.insert(vis[temp]); // vis[temp]=0;//清除标记,避免重复 temp=fail[temp]; } } return cnt; } int main() { int mm; cin>>n; { // memset(tree,0,sizeof(tree)); // memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { cin>>s; insert(i); } build(); int ans=0; cin>>mm; for(int i=1;i<=mm;i++) { m.clear(); cin>>ss;//文本串 if(search(ss)!=0) { ans++; cout<<"web "<<i<<": "; set<int>::iterator it; for(it=m.begin();it!=m.end();it++) { if(it==m.begin()) cout<<*it; else cout<<‘ ‘<<*it; } cout<<endl; } } cout<<"total: "<<ans<<endl; } }
原文:https://www.cnblogs.com/-citywall123/p/11307721.html