BZOJ 2342: [Shoi2011]双倍回文

BZOJ 2342: [Shoi2011]双倍回文

题意

给一个字符串S，求S一个最长的子串T满足T的长度是4的倍数，T是回文串且T的前半部分也是回文串。
|S|<=500000

分析

先建出回文树，注意到T必然是回文树上的一个节点，且T的后半部分必然是该节点fauk树上的祖先。
那么我们就在fail树上遍历，同时记录搜索栈中每种长度的出现次数即可。
其实回文树这个东西感觉跟ac自动机那棵树很想 好吧其实似乎就是没什么区别

代码

#include <bits/stdc++.h>const int N = 500005;struct Edge
{int to,next;
}e[N];int next[N];
int cnt;void addedge(int u,int v)
{e[++cnt].to = v; e[cnt].next = next[u]; next[u] = cnt;
}int n,sz,len[N],fail[N],ch[N][26],t[N],last,ans;
char s[N];void extend(int n,int c)
{int p = last;while (s[n - len[p] - 1] != s[n]) p = fail[p];if (!ch[p][c]){int now = ++sz, k = fail[p];len[now] = len[p] + 2;while (s[n - len[k] - 1] != s[n]) k = fail[k];fail[now] = ch[k][c];ch[p][c] = now;addedge(fail[now],now);}last = ch[p][c];
}void dfs(int x)
{t[len[x]]++;if (len[x] % 4 == 0 && t[len[x] / 2]) ans = std::max(ans,len[x]);for (int i = next[x]; i; i = e[i].next) dfs(e[i].to);t[len[x]]--;
}int main()
{scanf("%d%s",&n,s + 1);sz = 1; fail[0] = 1;len[1] = -1;for (int i = 1; i <= n; i++) extend(i,s[i]-'a');dfs(0);dfs(1);printf("%d",ans);
}