模板题
#include <cstdio>#include <algorithm>#include <cstring>#include <queue>#define MAXN 100005using namespace std;int n,m,siz;char a[MAXN],b[MAXN];vector<int> ans;struct tre{ int cnt,root; int nx[MAXN][128],fail[MAXN],end[MAXN]; int newnode() { cnt++; fail[cnt]=end[cnt]=0; for(int i=0;i<128;i++) nx[cnt][i]=0; return cnt; } void init() { cnt=siz=0; root=newnode(); } void insert(char *s,int id) { int now=root,len=strlen(s); for(int i=0;i<len;i++) { if(!nx[now][s[i]]) nx[now][s[i]]=newnode(); now=nx[now][s[i]]; } end[now]=id; } void build_fail() { queue<int> q; fail[root]=root; for(int i=0;i<128;i++) { if(!nx[root][i]) nx[root][i]=root; else fail[nx[root][i]]=root,q.push(nx[root][i]); } while(!q.empty()) { int now=q.front(); for(int i=0;i<128;i++) { if(nx[now][i]) { fail[nx[now][i]]=nx[fail[now]][i]; q.push(nx[now][i]); } else nx[now][i]=nx[fail[now]][i]; } q.pop(); } } void query(char *s,int id) { int len=strlen(s),now=root; ans.clear(); for(int i=0;i<len;i++) { now=nx[now][s[i]]; int t=now; while(t!=root) { if(end[t]) ans.push_back(end[t]); t=fail[t]; } } sort(ans.begin(),ans.end()); if(!ans.size()) return; PRintf("web %d:",id); for(int i=0;i<ans.size();i++) printf(" %d",ans[i]); printf("/n"); siz++; }}AC;int main(){ while(scanf("%d",&n)!=EOF) { AC.init(); for(int i=1;i<=n;i++) { scanf("%s",a); AC.insert(a,i); } AC.build_fail(); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%s",b); AC.query(b,i); } printf("total: %d/n",siz); } return 0;}新闻热点
疑难解答
