https://www.luogu.org/problem/show?pid=3121#sub
首先題目看清楚
FJ注意到列表中的單詞不會出現一個單詞是另一個單詞子串的情況，這意味著每個列表中的單詞在S中出現的開始位置是互不相同的
這意味著你在找答案時，當一個節點正常訪問的時候，你不用去尋找fail；
你只要在匹配失敗的時候取fail就好了；
關于fail的意義，可以看我AC自動機的博客；
然后我們在造trie時，順便把一個字符串的長度記錄下來；
end=一個字符串的長度；
然后我們開2個棧；
a[]記錄當前搜到那個點；
b[]記錄當前搜那個char；
然后如果發現當前節點是end；
直接彈出棧頂end個元素；
更新now指針，繼續搜；
好了；
有個事情要注意；
我原始的AC自動機；
void makezyy(){
for(
int i=
0;i<
26;i++)
if(T[
0].nxt[i])
q[++r]=T[
0].nxt[i];
while(r>l){
int x=
q[++l];
for(
int i=
0;i<
26;i++)
if(T[
x].nxt[i]){
q[++r]=T[
x].nxt[i];
int y=T[
x].fail;
while(
y&&!T[
y].nxt[i])
y=T[
y].fail;T[
q[r]].fail=T[
y].nxt[i];}}
}
void find(
int m){
int o=
0;
for(
int i=
0;i<
m;i++){
int x=
s[i]-
'a';
int y=o;
while(
y&&!T[
y].nxt[
x])
y=T[
y].fail;o=T[
y].nxt[
x];a[++tot]=o;b[tot]=i;
if(T[o].E){tot-=T[o].E;o=a[tot];} }
}
大家看，這個好理解，但是用了while循環，會被卡一個點；
那我們看看更優的寫法；
void makezyy(){
for(
int i=
0;i<
26;i++)
if(T[
0].nxt[i])
q[++r]=T[
0].nxt[i];
while(r>l){
int x=
q[++l];
for(
int i=
0;i<
26;i++)
if(!T[
x].nxt[i])T[
x].nxt[i]=T[T[
x].fail].nxt[i];
else{
q[++r]=T[
x].nxt[i];T[T[
x].nxt[i]].fail=T[T[
x].fail].nxt[i];}}
}
void find(
int m){
int o=
0;
for(
int i=
0;i<
m;i++){o=T[o].nxt[
s[i]-
'a'];a[++tot]=o;b[tot]=i;
if(T[o].E){tot-=T[o].E;o=a[tot];} }
}
種方法巧妙地運用地推；
兩種方法求出的fail值是相同的；
但是這種方法會無法辨別出某個節點在一開始有沒有某個兒子；
因為makezyy之后空的兒子自動變成了fail；
好像還可以優化的吧；
using namespace std;
struct trie{
int nxt[
26],fail,E;
}T[
100005];
int q[100005],l,r,a[
100005],b[
100005],tot;
int n,
m,ll;
char
s[
100005],c[
100005];
void init(
int m){
int o=
0;
for(
int i=
0;i<
m;i++){
int x=c[i]-
'a';
if(!T[o].nxt[
x])T[o].nxt[
x]=++ll;o=T[o].nxt[
x];}T[o].E=
m;
}
void makezyy(){
for(
int i=
0;i<
26;i++)
if(T[
0].nxt[i])
q[++r]=T[
0].nxt[i];
while(r>l){
int x=
q[++l];
for(
int i=
0;i<
26;i++)
if(!T[
x].nxt[i])T[
x].nxt[i]=T[T[
x].fail].nxt[i];
else{
q[++r]=T[
x].nxt[i];T[T[
x].nxt[i]].fail=T[T[
x].fail].nxt[i];}}
}
void find(
int m){
int o=
0;
for(
int i=
0;i<
m;i++){o=T[o].nxt[
s[i]-
'a'];a[++tot]=o;b[tot]=i;
if(T[o].E){tot-=T[o].E;o=a[tot];} }
}
int main()
{scanf(
"%s",
s);scanf(
"%d",&n);
while(n--)scanf(
"%s",c),init(strlen(c));makezyy();find(strlen(
s));
for(
int i=
1;i<=tot;i++)cout<<
s[b[i]];
}
轉載于:https://www.cnblogs.com/largecube233/p/6797890.html
總結
以上是生活随笔為你收集整理的AC自动机-洛谷3121 [USACO15FEB]审查（黄金）Censoring (Gold)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
