生活随笔
收集整理的這篇文章主要介紹了
[AC自动机]luoguP3966
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
模板題和一些坑點：
1.輸入的單詞可能會有重復的，重復的單詞不用重復計算，將相同單詞的最小id保存下來就行
2.樸素的AC自動機算法最后一個點會T，用last優化，直接跳到單詞末節點，效率提高十分顯著。
代碼如下：
#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define ll long long
#define INF 0x3f3f3f3f
#define CLR(a) memset(a, 0, sizeof(a))
using namespace std
;
const int maxn
=1e6+300;
int vis
[205],n
,mp
[205];
struct Trie
{int nxt
[maxn
][27],fail
[maxn
],end
[maxn
],lst
[maxn
]; int cnt
; void insert(char buf
[],int id
){int len
=strlen(buf
);int now
=0;for ( int i
=0;i
<len
;i
++ ){int x
=buf
[i
]-'a';if (!nxt
[now
][x
]) nxt
[now
][x
]=++cnt
;now
=nxt
[now
][x
];}if(!end
[now
]) end
[now
]=id
;mp
[id
]=end
[now
];}void build(){queue
<int>q
;for (int i
=0;i
<26;i
++) if(nxt
[0][i
]) q
.push(nxt
[0][i
]);while (!q
.empty()){int now
=q
.front();q
.pop();for ( int i
=0;i
<26;i
++ ){int x
=nxt
[now
][i
];if (!x
) nxt
[now
][i
]=nxt
[fail
[now
]][i
];else{ fail
[x
]=nxt
[fail
[now
]][i
];lst
[x
]=end
[fail
[x
]]?fail
[x
]:lst
[fail
[x
]];q
.push(x
);}}}}void query(char buf
[]){ int len
=strlen(buf
);int now
=0;int res
=0;for ( int i
=0;i
<len
;i
++ ) { if(buf
[i
]=='#'){now
=0;continue;}now
=nxt
[now
][buf
[i
]-'a'];if(end
[now
]) vis
[end
[now
]]++;int tmp
=lst
[now
];while ( tmp
){vis
[end
[tmp
]]++;tmp
=lst
[tmp
];}}for(int i
=1;i
<=n
;i
++) printf("%d\n",vis
[mp
[i
]]);}
}ac
;
char buf
[maxn
],s
[maxn
];
int main() {scanf("%d",&n
);for(int i
=1;i
<=n
;i
++){CLR(s
);scanf("%s",s
);ac
.insert(s
,i
);int len
=strlen(s
);s
[len
]='#';strcat(buf
,s
);} ac
.build();ac
.query(buf
);return 0;
}
總結
以上是生活随笔為你收集整理的[AC自动机]luoguP3966的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
