回文自动机！
正着跑一遍 记录以每个点作为回文子串的右端点的最大长度
倒过来跑一遍 记录每个点作为左端点的最大长度
求个和就好啦
附代码。
#include#include #include #include #define inf 20021225#define ll long long#define mxn 100010using namespace std;struct node{int fa,ch[26],len;}t[mxn];int poi,lt,f[mxn],s[mxn],n,len,ans;char ch[mxn];void init(){ memset(s,0,sizeof(s)); for(int i=0;i<=poi;i++) memset(t[i].ch,0,sizeof(t[i].ch)),t[i].fa=t[i].len=0; s[0] = -1; t[1].fa = t[0].fa =1; t[1].len = -1; t[0].len = 0; poi = lt = 1; n=0;}int id(char c){return c-'a';}void extend(int c,int b,int id){ //printf("%d\n",c); int p = lt; s[++n] = c; while(s[n-1-t[p].len]!=c) 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]!=c) np = t[np].fa; t[q].fa = t[np].ch[c]; t[p].ch[c] = q; } lt = t[p].ch[c]; if(b) f[id+1] = t[lt].len; else ans=max(f[id]+t[lt].len,ans);}int main(){ scanf("%s",ch); len = strlen(ch); init(); for(int i=0;i
这玩意跑的奇快无比。