回文自动机简述
其实不算毒瘤，与AC自动机比较相似。
定义
回文自动机是有两棵树的森林，其处理了一个字符串中以某字符结尾的全部回文串。
其中一棵是长度为偶数的回文串集合，根为0，另一棵是长度为奇数的回文串集合，根为1。
对于串abbaabba的回文自动机如下
从网上随便找了张图
实现方法
回文串在回文自动机中实际上只存了一半。
如上图的7号节点，代表回文串baab,3号节点代表回文串b
理解自动机的关键就是理解(fail)指针，回文自动机的(fail)定义如下
对于节点i
回文自动机的fail，为i所代表的回文串的最长回文真后缀的那个点。
那么当我们匹配i+1失配时,我们可以跳到fail[i]然后比较fail所代表的回文串的前一个字符是否与i+1相等。
如此递归，直到跳到根，那么i+1的回文长度 len[i+1]=1否则len[i+1]=len[匹配到的fail]+1;
如何构建fail指针？
就如同AC自动机一样，我们考虑用上一个回文串的fail来构建这个新插入点的fail
我们先判断i这个字符是不是等于上一个串的fail串前一个，如果是就匹配成功。
否则继续沿着fail指针跳，边跳边判断就可以了。
(Problem List)
(1.)洛谷P1872回文串计数
(2.)[APIO2014]回文串
(Solution)
(1.)板子题。
/*
@Date : 2019-07-15 16:33:37
@Author : Adscn (adscn@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
IL void pi(int k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
#define int long long
const int N=2e4+7;
char a[N];
long long l[N];
struct PAM{
struct node
{
int c[26];
int fail,len;
node(){fail=len=0;}
}t[N];
int num[N];
char S[N];
int n,cnt;
explicit PAM()
{
n=0;
cnt=1;
t[1].len=-1;
t[0].fail=1;
}
inline int getfail(int x)
{
while(S[n]^S[n-t[x].len-1])x=t[x].fail;//这就是为什么t[1].len要等于-1
return x;
}
inline int insert(int x)
{
S[++n]=(x-='a');
int cur=getfail(last);
if(!t[cur].c[x])
{
int nw=++cnt;
t[nw].fail=t[getfail(t[cur].fail)].c[x];
t[nw].len=t[cur].len+2;
t[cur].c[x]=nw;
num[nw]=num[t[nw].fail]+1;
}
last=t[cur].c[x];
//++t[last].cnt;
return num[last];
}
int last;
}x,y;
long long ans;
signed main(void)
{
cin>>(a+1);
int len=strlen(a+1);
for(int i=1;i<=len;++i)l[i]=l[i-1]+x.insert(a[i]);
for(int i=len;i>1;--i)ans+=1ll*l[i-1]*y.insert(a[i]);
cout<<ans;
return 0;
}
(2.)更加板子是smg
在fail树上累加cnt即可。
注意当我们将fail树上的儿子的贡献累加到父亲时，我们不必进行dfs
因为fail[x]<x,所以我们直接从n枚举到1就可以了
/*
@Date : 2019-07-15 17:54:11
@Author : Adscn (adscn@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
IL void pi(int k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
const int N=3e5+7;
struct PAM{
int n;
int fail[N],cnt[N],c[N][26],len[N];
int S[N];
int last,tot;
PAM()
{
tot=1,n=0;
fail[0]=1,len[1]=-1;
}
inline int getfail(int x)
{
while(S[n]^S[n-len[x]-1])x=fail[x];
return x;
}
inline void add(int x)
{
S[++n]=(x-='a');
int cur=getfail(last);
if(!c[cur][x])
{
int nw=++tot;
fail[nw]=c[getfail(fail[cur])][x];
len[nw]=len[cur]+2;
c[cur][x]=nw;
}
++cnt[last=c[cur][x]];
}
void init()
{
static char s[N];
cin>>(s+1);
int Siz=strlen(s+1);
for(int i=1;i<=Siz;++i)add(s[i]);
}
}x;
int main(void)
{
x.init();
long long ans=0;
for(int i=x.tot;i;--i)x.cnt[x.fail[i]]+=x.cnt[i],ans=max(ans,1ll*x.cnt[i]*x.len[i]);
cout<<ans;
return 0;
}