http://acm.hdu.edu.cn/showproblem.php?pid=2896
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<vector> using namespace std; int n,m,len,tot=1,cnt; char s[501],ss[10001]; int trie[100001][133],f[100001]; queue<int>q; int v[100001]; bool use[501]; void insert(int k) { int root=1;len=strlen(s); for(int i=0;i<len;i++) { int id=s[i]; if(!trie[root][id]) trie[root][id]=++tot; root=trie[root][id]; } v[root]=k; } void getfail() { for(int i=0;i<=132;i++) trie[0][i]=1; q.push(1); while(!q.empty()) { int now=q.front(); for(int i=0;i<=132;i++) { if(!trie[now][i]) continue; q.push(trie[now][i]); int j=f[now]; while(!trie[j][i]) j=f[j]; f[trie[now][i]]=trie[j][i]; } q.pop(); } } void work(int k) { len=strlen(ss); bool ok=false;int root=1; memset(use,false,sizeof(use)); for(int i=0;i<len;i++) { int id=ss[i]; while(!trie[root][id]) root=f[root]; root=trie[root][id]; if(v[root]) { int j=root; ok=true; while(j) { if(v[j]) use[v[j]]=true; j=f[j]; } } } if(ok) { cnt++; printf("web %d:",k); for(int i=1;i<=n;i++) if(use[i]) printf(" %d",i); printf("\n"); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",s); insert(i); } getfail(); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%s",ss); work(i); } printf("total: %d\n",cnt); }
2个理解误区
1、insert函数中最后v[root]=k不会造成覆盖
因为除非是完全相同的字符串,负责均从1号节点向下构造,不会在同一个节点有超过1的标记
2、统计答案时,不一定非要对统计过的清0,这里是多模式匹配多个字符串,清0了下一个就不能用了,为了防止重复所以增设use数组,判断是否出现过
当然也可以对v数组开一个备用数组,每次恢复
原文:http://www.cnblogs.com/TheRoadToTheGold/p/6490655.html