社区讨论

关于PAM

ssuisdavid
学术版参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo2w3tnt
此快照首次捕获于
2023/10/23 20:44
2 年前
此快照最后确认于
2023/10/23 20:44
2 年前
查看原帖
今天在做P5555时，我意外地把PAM中两句语句调换了顺序。这是错误的PAM代码
CPP
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代码：
CPP
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指针，不知道为什么这样就会导致错误。

回复

共 1 条回复，欢迎继续交流。

正在加载回复...