回文自动机

小小总结:

  1. 别忘了写上初始化!
  2. 当字符串下标从 0 0 0开始时, p o s pos pos初始化为 1 -1 1;若从 1 1 1开始,则 p o s pos pos初始化为 0 0 0;最终的 p o s pos pos代表最后一个字符的下标(前者为 n 1 n-1 n1,后者为 n n n)。
  3. 根据本质不同的回文子串数量不超过 s |s| s,回文树节点数不超过 n + 2 n+2 n+2
  4. 节点 0 0 0下面的回文串长度为偶数,节点 1 1 1下面的回文串长度为奇数,而第一个字符在加入时显然只能构成奇数长度(长度为 1 1 1)的回文子串,因此 l a s t last last初始化为 1 1 1比较好。
  5. 写法与后缀自动机很像,但如果只有后缀插入的话节点编号是递增的,统计 e n d p o s endpos endpos数( c n t cnt cnt值)时无需进行计数排序。
  6. 若要将两个字符串连在一起建立回文自动机,则必须真的将两个字符串连接在一起,因为函数内部要调用这个连接后的字符串(中间插入两个不同且不使用的字符)。
  7. 推荐一篇入门文章

上板子

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 3e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn];
int ch[maxn][26], fail[maxn], len[maxn], cnt[maxn], half[maxn];
int last, tot, pos;

void init() {
    fail[0]=fail[1]=tot=last=1;
    len[1]=pos=-1;
}

void add(int c) {
    ++pos; int p=last;
    while(s[pos-len[p]-1]!=s[pos]) p=fail[p];
    if(!ch[p][c]) {
        int np=++tot, fp=fail[p];
        len[np]=len[p]+2;
        while(s[pos-len[fp]-1]!=s[pos]) fp=fail[fp];
        fail[np]=ch[fp][c];
        if(len[fail[np]]<=len[np]/2) half[np]=fail[np]; //此处if,else用于求half数组
		else {
			int hp=half[p];
			while(len[hp]+2>len[np]/2||s[pos-len[hp]-1]!=s[pos]) hp=fail[hp];
			half[np]=ch[hp][c];
		}
		ch[p][c]=np; //ch[p][c]的更新一定要放最后,因为当p=1时,p=fail[p],会影响前面fail[np]的更新
    }
    last=ch[p][c];
    cnt[last]++;
}

int main() {
    //ios::sync_with_stdio(false);
    scanf("%s", s);
    init();
    for(int i=0; s[i]; ++i) add(s[i]-'a');
    for(int i=tot; i; --i) cnt[fail[i]]+=cnt[i];
}