警示后人(70pts,WA on #1 #5 #10)
查看原帖
警示后人(70pts,WA on #1 #5 #10)
569235
w9095楼主2025/6/28 08:57

注意在 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);
}

2025/6/28 08:57
加载中...