注意在 AC 自动机上跑匹配时,如果先在当前节点插入再走到下一个节点,注意最后一个走到节点会没有更新导致 WA。
WA:
void match_ac(int p,string t)
{
int x=0,l=t.size();
for(int i=0;i<l;i++)
{
int id=t[i]-'a';
insert(rt[x],1,m,p),x=trie[x][id];
}
}
AC:
void match_ac(int p,string t)
{
int x=0,l=t.size();
for(int i=0;i<l;i++)
{
int id=t[i]-'a';
insert(rt[x],1,m,p),x=trie[x][id];
}
insert(rt[x],1,m,p);
}