算法学习—————PAM回文自动机


时隔一年,第一次学习新的算法

原理和AC自动机差不多

基本思想:

  1. 两棵树分别代表奇偶

  2. 在一个回文串两边同时填上相同字符可以得到另一个回文串,以此构建两棵树

树上维护信息:

  1. 节点表示的回文串为当前位置的最长回文串

  2. 节点上维护当前位置最长回文串的长度,fail指针(当前回文串的最长回文后缀)

如何维护:

  1. 若可以扩展,长度+2 判断条件: s[pos-len-1] == s[pos],否则跳fail

  2. 如何维护fail? 找到第一个可以扩展的位置,连出c边的点即是fail的指向

代码为洛谷模板题

当前节点的答案为他的fail的答案+1(可想而知,感觉而知)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define O(x) cout<<#x<<" "<<x<<endl;
#define B cout<<"Breakpoint"<<endl;
using namespace std;
int read(){
	int x = 1,a = 0;char ch = getchar();
	while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
	while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
	return x*a;
}
const int maxn = 5e5+10;
struct node{
	int len,fail,ch[30];
}pam[maxn];
char s[maxn];
int n,preNode = 2,tot = 2;
int ans[maxn];
void insert(int pos){
	if (pos > 1) s[pos] =  (s[pos] - 97 + ans[preNode]) % 26 + 97;
	int c = s[pos]-'a';
	while (s[pos - pam[preNode].len - 1] != s[pos]) preNode = pam[preNode].fail;
	if (pam[preNode].ch[c]) preNode = pam[preNode].ch[c];
	else{
		int nowNode = ++tot;
		pam[preNode].ch[c] = nowNode;
		pam[nowNode].len = pam[preNode].len + 2;
		if (preNode == 1) pam[nowNode].fail = 2; 
		else{
			for (preNode = pam[preNode].fail;s[pos - pam[preNode].len - 1] != s[pos];preNode = pam[preNode].fail);
			pam[nowNode].fail = pam[preNode].ch[c];
		}
		preNode = nowNode;
	}
	ans[preNode] = ans[pam[preNode].fail] + 1;
	cout<<ans[preNode]<<" ";
}
int main(){
	scanf ("%s",s+1);
	n = strlen(s+1);
	pam[1].len = -1,pam[2].len = 0;
	pam[2].fail = 1;
	for (int i = 1;i <= n;i++) insert(i);
	return 0;
}

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/288002.html

(0)
上一篇 2022年9月6日
下一篇 2022年9月6日

相关推荐

发表回复

登录后才能评论