构建

插入和匹配

$$N = x C x$$

$fail(N)=xC’x$

int find(int x){
while(s[n-t[x].len-1]!=s[n])
x=t[x].fail;
return x;
}
s[++n]=x;
int cur=find(last);
if (!t[cur].vis[x]){
t[++siz].fail=t[find(t[cur].fail)].vis[x];
t[cur].vis[x]=siz;t[siz].len=t[cur].len+2;
}
last=t[cur].vis[x];t[last].cnt++;
}

应用

例：[APIO2014]回文串

代码
#include <bits/stdc++.h>
#define chkmax(a,b) (a<b?a=b:0)
using namespace std;
const int maxn=300005;
typedef long long ll;
class Palindrome_Automaton{
private:
class node{
public:
int len,cnt,fail;
int vis[26];
};
node t[maxn];
int last,n,siz,s[maxn];
int find(int x){
while(s[n-t[x].len-1]!=s[n])
x=t[x].fail;
return x;
}
public:
void init(){
s[0]=-1;
t[siz=1].len=-1;
t[0].fail=1;
}
s[++n]=x;
int cur=find(last);
if (!t[cur].vis[x]){
t[++siz].fail=t[find(t[cur].fail)].vis[x];
t[cur].vis[x]=siz;t[siz].len=t[cur].len+2;
}
last=t[cur].vis[x];t[last].cnt++;
}
ll count(){
ll res=0;
for (int i=siz;~i;--i){
t[t[i].fail].cnt+=t[i].cnt;
chkmax(res,1ll*t[i].cnt*t[i].len);
}
return res;
}
}T;
char s[maxn];
int len;
int main(){
scanf("%s",s),len=strlen(s);
T.init();
for (int i=0;i<len;++i)
}