用 bfs 离线构造的广义自动机的代码如下

int insert(int c,int last){
	int k=ch[last][c],p=link[last];
	if(len[k]) return k;
	len[k]=len[last]+1;
	for(;p!=-1&&!ch[p][c];p=link[p]) ch[p][c]=k;
	if(p==-1) link[k]=0;
	else{
		int q=ch[p][c];
		if(len[q]==len[p]+1) link[k]=q;
		else{
			int nk=++tot;link[nk]=link[q],len[nk]=len[p]+1;
			for(int i=0;i<26;i++) if(len[ch[q][i]]) ch[nk][i]=ch[q][i];
			for(;p!=-1&&ch[p][c]==q;p=link[p]) ch[p][c]=nk;
			link[k]=link[q]=nk;
		}
	}
	return k;
}

其中特判

if(len[k]) return k;

能否去掉，模板题我去掉了以后能够AC，并且手玩了很久感觉不会出现提前赋值的情况