在写 【模板】AC自动机(二次加强版) 这道题时,我在本题的代码上进行了微调,却发现过不了上面那题的样例。
后来我发现在查询中,我错误地将 p 的初始值赋成了 1,而我建 trie 树时是以 0 为根的。
void AC_que(char *s)
{
int len=strlen(s+1),p=1,ans=0;
// 字典树我是以 0 为根,而这里手误打成了 p=1
for(int i=1;i<=len;i++)
{
int c=s[i]-'a';p=AC[p].son[c];
for(int j=p;j;j=AC[j].Fail)
cnt[AC[j].ed]++;
}
}
hack 数据为:
input:
2
a
aa
abbb
0
output:
1
a
而按照上面的错误写法会输出:
1
a
aa
这是被 hack 的代码:https://www.luogu.com.cn/record/57751566
这是修改后的代码:https://www.luogu.com.cn/record/57752095
两份代码在目前数据均能通过,但后者才是正解。