今天在做P5555时，我意外地把PAM中两句语句调换了顺序。这是错误的PAM代码

struct PAM
{
	int len[maxn],fail[maxn],ch[maxn][26],tot,lst;string s;
	PAM()
	{
		tot=1;fail[0]=1;len[1]=-1;
	}
	int getfail(int u,int i)
	{
		while (i-len[u]-1<0||s[i-len[u]-1]!=s[i])
		{
			u=fail[u];
		} 
		return u;
	} 
	void _insert(int i)
	{
		int id=s[i]-'a',p=getfail(lst,i);
		if (!ch[p][id])
		{
			
			ch[p][id]=++tot;
			len[tot]=len[p]+2;
			fail[tot]=ch[getfail(fail[p],i)][id];
		}
		lst=ch[p][id];
	}
}

---

这是正确的PAM代码：

struct PAM
{
	int len[maxn],fail[maxn],ch[maxn][26],tot,lst;string s;
	PAM()
	{
		tot=1;fail[0]=1;len[1]=-1;
	}
	int getfail(int u,int i)
	{
		while (i-len[u]-1<0||s[i-len[u]-1]!=s[i])
		{
			u=fail[u];
		} 
		return u;
	} 
	void _insert(int i)
	{
		int id=s[i]-'a',p=getfail(lst,i);
		if (!ch[p][id])
		{
			fail[++tot]=ch[getfail(fail[p],i)][id];
			ch[p][id]=tot;
			len[tot]=len[p]+2;
		}
		lst=ch[p][id];
	}
}

---

两者区别在于加入新节点时，是先处理fail指针，还是先处理ch指针，不知道为什么这样就会导致错误。