时隔一年,第一次学习新的算法
原理和AC自动机差不多
基本思想:
-
两棵树分别代表奇偶
-
在一个回文串两边同时填上相同字符可以得到另一个回文串,以此构建两棵树
树上维护信息:
-
节点表示的回文串为当前位置的最长回文串
-
节点上维护当前位置最长回文串的长度,fail指针(当前回文串的最长回文后缀)
如何维护:
-
若可以扩展,长度+2 判断条件: s[pos-len-1] == s[pos],否则跳fail
-
如何维护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;
}
标签:ch,pos,PAM,fail,自动机,preNode,pam,回文
From: https://www.cnblogs.com/little-uu/p/16662959.html