AC自动机中有一个很关键的失配指针 fail，引导当前值失配后应当前往哪一个状态．

但是，fail 只是前往最深的失配位置,而没有保证下一次一定会到可以匹配的地方.

在从 KMP 算法推广到 AC 自动机的时候,因为是自己写的AC 自动机,所以我加入了一个 nxt 数组,保存当前位失配且下一位是字符j时应当前往哪一个状态,以此做到O(1)失配.

fail[x]=nxt[fail[fa[x]]][val[x]];
if(fail[x]==x)fail[x]=0;
rd(i,26){
	if(trie[x][i])nxt[x][i]=trie[x][i];
	else {
		if(fail[x]!=x)nxt[x][i]=nxt[fail[x]][i];
	}
	if(trie[x][i])q.push(trie[x][i]);
}

这是我构建 AC 自动机的过程,因此,在失配转移的时候复杂度较为严格

for(int i=0;i<s.size();i++){
	cyr=nxt[cyr][s[i]-'a'];
	if(res[cyr])ans[cyr]=res[cyr];
}

直到今天我做题的时候,发现别人的空间比我的小很多($\dfrac{1}{2}$).然后发现主流的(至少我见到的)AC自动机写法是暴力跳失配的(如果我的理解有误请指出,谢谢).

所以我比较好奇:

1. 主流的AC自动机写法是不是暴力跳的?

2. 如果是,为什么暴力跳是对的?

3. 我自己长期在写的这个东西是什么?