回文自动机板子题~
回文自动机和ACA以及SAM都是很类似的[毕竟都是自动机吗233]
回文自动机的树形结构是 fail指针构成的
用增量法 构造即可
（其实我也没完全学懂呢T^T）
#include#include #include #include #define inf 20021225#define ll long long#define mxn 310000using namespace std;struct node{int ch[26],len,fa,s;}t[mxn];// ch add character fa fail s timeschar ch[mxn]; int lt,poi,s[mxn],n; ll ans;void init(){ s[0]=-1; t[0].len=0; t[1].len=-1; t[0].fa=1; t[1].fa=1; poi=lt=1;}int id(char c){return c-'a';}void extend(int c){ int p=lt; s[++n]=c; while(s[n-1-t[p].len] != s[n]) p=t[p].fa; if(!t[p].ch[c]) { int q=++poi; t[q].len=t[p].len+2;int np = t[p].fa; while(s[n-1-t[np].len] != s[n]) np=t[np].fa; t[q].fa=t[np].ch[c]; t[p].ch[c]=q; } lt=t[p].ch[c]; t[lt].s++;}void calc(){ for(int i=poi;~i;i--) t[t[i].fa].s += t[i].s; for(int i=0;i<=poi;i++) ans=max(ans,1ll*t[i].len*t[i].s);}int main(){ scanf("%s",ch); init(); int n = strlen(ch); for(int i=0;i