算法学习—————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;
}