?

網(wǎng)上很多代碼都略顯繁瑣，看了一下yy dalao的代碼感覺很好，但他懶得打題解（好吧我也是

以0為根節(jié)點的話，我把yy的一段代碼刪了改用fail[c]=x==0?0:ch[fail[x]][i];來實現(xiàn)特判，效果還不錯！
也算是AC自動機(jī)的模版題吧，用了一個id數(shù)組來儲藏每一個特征碼的最后一個字符所在位置，再用vis來看網(wǎng)站源碼中有哪條特征碼（即哪條特征碼的id被訪問到)

1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 char s[205],t[10005]; 5 int fail[100001],q[100002],ch[100002][130],val[100002],id[505],vis[100002]; 6 int sz=0,ans=0,n; 7 void trie(int x) 8 { 9 int u=0,m=strlen(s); 10 for(int i=0;i<m;i++) 11 { 12 int c=s[i]; 13 if(!ch[u][c]) 14 ch[u][c]=++sz; 15 u=ch[u][c]; 16 } 17 id[x]=u; 18 val[u]++; 19 } 20 void makefail() 21 { 22 int head=0,tail=1; 23 q[1]=0;fail[0]=0; 24 while(head!=tail) 25 { 26 int x=q[++head];if(head>=100000)head=0; 27 for(int i=0;i<128;i++){ 28 int c=ch[x][i]; 29 if(!c){ch[x][i]=ch[fail[x]][i];continue;} 30 q[++tail]=c;if(tail>=100000)tail=0; 31 fail[c]=x==0?0:ch[fail[x]][i]; 32 } 33 } 34 } 35 void ac(int x) 36 { 37 int f=0,k=0,len=strlen(t); 38 memset(vis,0,sizeof(vis)); 39 for(int i=0;i<len;i++){ 40 int u=t[i]; 41 k=ch[k][u]; 42 for(int j=k;j;j=fail[j]){if(val[j]){f=1;vis[j]=1;}} 43 } 44 if(!f)return; 45 ans++;printf("web %d:",x); 46 for(int i=1;i<=n;i++) 47 if(vis[id[i]])printf(" %d",i); 48 printf("\n"); 49 } 50 int main() 51 { 52 int m; 53 scanf("%d",&n); 54 for(int i=1;i<=n;i++){ 55 scanf("%s",s); 56 trie(i); 57 } 58 makefail(); 59 scanf("%d",&m); 60 for(int i=1;i<=m;i++) 61 { 62 scanf("%s",t); 63 ac(i); 64 } 65 printf("total: %d\n",ans); 66 return 0; 67 } hdu2896

?

轉(zhuǎn)載于:https://www.cnblogs.com/JKAI/p/6914583.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【HDU2896】病毒侵袭——ac自动机的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。