回文自动机

回文自动机

参考： 回文树

// Created by CAD
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=3e5+5;
namespace pam{
    int sz,tot,last;
    int len[maxn],fail[maxn],cnt[maxn];//该节点对应回文子串长度、后缀链接
    char s[maxn];                      //保存已存入自动机的字符
    int Next[maxn][26];            //转移
    int node(int l){
        len[++sz]=l;
        fail[sz]=cnt[sz]=0;
        return sz;
    }
    void init(){                       //记得初始化
        sz=-1;
        s[tot=0]='$';
        node(0),node(-1);
        fail[0]=1,last=0;
    }
    int getfail(int x){
        while(s[tot-len[x]-1]!=s[tot]) x=fail[x];
        return x;
    }
    void insert(char c){
        s[++tot]=c;
        int now=getfail(last);
        if(!Next[now][c-'a']){           //主要是用于判别单字符是否存在，既-1节点的转移
            int id=node(len[now]+2);
            fail[id]=Next[getfail(fail[now])][c-'a'];
            Next[now][c-'a']=id;
        }
        last=Next[now][c-'a'];
        cnt[last]++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    pam::init();
    string s;cin>>s;
    for(auto i:s)
        pam::insert(i);

    return 0;
}