想知道484每个萌新oier在最初知道AC自动机的时候都会理解为自动AC稽什么的,,,反正我记得我当初刚知道这个东西的时候,我以为是什么神仙东西$hhhhh$
首先要学AC自动机,就要先学会俩知识点:
trie树和kmp(我记得我都写了学习笔记,,,然而写得太烂了不想放上来了,,,网上随便搜篇题解都写得比我好的样子TT
好的那就当做已经掌握了这俩了来学习AC自动机趴!
首先要知道AC自动机是解决什么东西的嘛QwQ
kmp是一对一嘛,就是说一个字符串匹配一个字符串
然后AC自动机就是解决它没有解决的问题——一对多,一个字符串匹配多个字符串
这方面的题目比较多问法什么的也比较多我就以板子题1为例学下这个知识点好了QAQ
首先我们就读入所有模式串,建一棵trie树
然后就建fail指针
先说说fail指针是干什么的趴QwQ
举个eg好了,假如模式串有ace acd say she shr her ced 然后文本串是aced
于是构出来的trie树长这样(,,,图咕了$QAQ$
假如我们现在再匹配ace,那就当匹配到e之后就没有辣,那我们就找有麻油还能匹配的呢
那我们就和之前想kmp的时候一样,想着怎么利用之前做了的事儿呢,就想到,假如我能匹配ace,我就一定也能匹配ce,就一定也能匹配e这样子的对趴
所以我们就找啊,找trie树上有麻油一个点它及它之前的字符串和ace的后缀相同的
这个就是fail指针的作用了——记录每个点的表示的字符串的最长后缀指向哪个点
明白了麻油!我jio得还挺好理解的!
哦对了我好像没有解释为什么是最长后缀,,,?其实我jio得挺显然的?就是因为假如我有个ac还有个a,那我如果指向ac之后等ac匹配完了自然会去a的,可是如果指向的是a它不可能再指向ac了
get?
好大概思路就是这样的,具体实现和代码等下再说趴,,,QAQ
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define rp(i,x,y) for(register ll i=x;i<=y;++i) const ll N=;
ll n,cnt,as;
struct tre{ll ed,nxt[],fail;tre(){ed=;memset(nxt,,sizeof(nxt));fail=;}}tr[N]; inline ll read()
{
register char ch=getchar();register ll x=;register bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=getchar();
if(ch=='-')ch=getchar(),y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();
return y?x:-x;
}
inline void bd(string x)
{
ll lth=x.length()-,nwtr=;
rp(i,,lth){if(tr[nwtr].nxt[x[i]-'a'+]==)tr[nwtr].nxt[x[i]-'a'+]=++cnt;nwtr=tr[nwtr].nxt[x[i]-'a'+];}
++tr[nwtr].ed;
}
inline void fl()
{
queue<ll>Q;
rp(i,,)if(tr[].nxt[i])Q.push(tr[].nxt[i]);
while(!Q.empty())
{
ll nw=Q.front();Q.pop();
rp(i,,)
{
if(tr[nw].nxt[i]){tr[tr[nw].nxt[i]].fail=tr[tr[nw].fail].nxt[i];Q.push(tr[nw].nxt[i]);}
else tr[nw].nxt[i]=tr[tr[nw].fail].nxt[i];
}
}
}
inline void zdj(string str)
{
ll lth=str.length()-,nw=;
rp(i,,lth)
{
nw=tr[nw].nxt[str[i]-'a'+];
for(ll t=nw;t && tr[t].ed!=-;t=tr[t].fail)
{
as+=tr[t].ed;
tr[t].ed=-;
}
}
printf("%d\n",as);
} int main()
{
n=read();rp(i,,n){string str;cin>>str;bd(str);}fl();
string str;cin>>str;zdj(str);
return ;
}
这题要注意下,,,我只开大了点儿就MLE了QAQ!
umm我想了下,把几个板子题都放这儿好了QAQ
这是板子2号
这题差不多啊,就先把trie树建起来,fail按套路求一下,然后注意一下的是计数的时候有个小技巧,就是可以让是结尾的节点的end=单词号,非结尾的=0,然后每次在文本串中扫到的时候就直接as[end]++就好了,没了
哦还有一个,,,题解第二个的方法似乎很妙,一个优化,一个树上dp,有时间再搞,QAQ
放下代码QAQ
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define rp(i,x,y) for(register ll i=x;i<=y;++i) const ll N=,M=;
ll n,cnt,as;
struct tre
{
ll ed,nxt[],fail,cs;
void clr(){ed=;memset(nxt,,sizeof(nxt));fail=;}
}tr[N];
struct ans{ll pos,as;void clr(){as=;pos=;}}ass[M];
bool gdgs=;
string str[M]; inline ll read()
{
register char ch=getchar();register ll x=;register bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=getchar();
if(ch=='-')ch=getchar(),y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();
return y?x:-x;
}
inline bool cmp(ans gd,ans gs){return gd.as==gs.as?gd.pos<gs.pos:gd.as>gs.as;}
inline void bd(ll nm)
{
cin>>str[nm];ass[nm].clr();ass[nm].pos=nm;ll lth=str[nm].length()-,nw=;
rp(i,,lth)
{
if(tr[nw].nxt[str[nm][i]-'a'+]==)tr[nw].nxt[str[nm][i]-'a'+]=++cnt,tr[cnt].clr();
nw=tr[nw].nxt[str[nm][i]-'a'+];
}
tr[nw].ed=nm;
}
inline void fl()
{
queue<ll>Q;
rp(i,,)if(tr[].nxt[i])Q.push(tr[].nxt[i]);
while(!Q.empty())
{
ll nw=Q.front();Q.pop();
rp(i,,)
{
if(tr[nw].nxt[i])tr[tr[nw].nxt[i]].fail=tr[tr[nw].fail].nxt[i],Q.push(tr[nw].nxt[i]);
else tr[nw].nxt[i]=tr[tr[nw].fail].nxt[i];
}
}
}
inline void zdj()
{
string str;cin>>str;ll lth=str.length()-,nw=;
rp(i,,lth)
{
nw=tr[nw].nxt[str[i]-'a'+];
for(register ll j=nw;j;j=tr[j].fail)++ass[tr[j].ed].as;
}
} int main()
{
while(gdgs)
{
n=read();if(!n)exit();tr[].clr();cnt=;rp(i,,n)bd(i);fl();tr[].fail=;zdj();
sort(ass+,ass+n+,cmp);printf("%d\n",ass[].as);
cout<<str[ass[].pos]<<endl;rp(i,,n)if(ass[i].as==ass[i-].as)cout<<str[ass[i].pos]<<endl;else break;
}
return ;
}
,,,玄学事件?我开始打的是for(i)里套个for(i)也过去辣QAQ?
然后放下被安利的题目:
阿最后说一下,还有一个小优化叫$last$优化,就将$fail$再优化了下,复杂度是没变的但实际上常有奇效$QwQ$