hack
查看原帖
hack
338630
Silence_water楼主2021/9/10 11:33

在写 【模板】AC自动机(二次加强版) 这道题时,我在本题的代码上进行了微调,却发现过不了上面那题的样例。

后来我发现在查询中,我错误地将 pp 的初始值赋成了 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

两份代码在目前数据均能通过,但后者才是正解。

2021/9/10 11:33
加载中...