原题链接
题目描述：顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。 输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。
输入格式：一行由小写英文字母组成的字符串S。
输出格式：一行一个整数，表示最长双回文子串的长度。
样例输入： baacaabbacabb
样例输出： 12
解析：看到回文串似乎就会想到manacher。 首先跑一遍manacher。 关键是接下来怎么做，如果强行枚举断点会变成\(O(n^2)\)。 设l[i]表示右端点为i的回文串的最长长度，r[i]表示左端点为i的回文串的最长长度。 那么可以在manacher的同时求出l[i]和r[i]的初值。 l[i + hw[i] - 1] = max(l[i + hw[i] - 1], hw[i] - 1) r[i - hw[i] + 1] = max(r[i - hw[i] + 1], hw[i] - 1) 最后再递推求出最终的l[i]和r[i] l[i] = max(l[i], l[i + 2] - 2) r[i] = max(r[i], r[i - 2] - 2) 最后枚举每一个添加进去的字符，答案即为max{l[i] + r[i]}。
代码如下：
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 1e5 + 5; int n, hw[maxn << 1], ans, l[maxn << 1], r[maxn << 1]; char s[maxn << 1]; void prepare(void) { s[n << 1] = '#'; for (int i = n; i ; -- i) { s[i * 2 - 1] = s[i]; s[i * 2 - 2] = '#'; } n <<= 1; } void manacher(void) { prepare(); int mid = 0, mr = 0; for (int i = 1; i <= n; ++ i) { if (i < mr) hw[i] = min(hw[mid * 2 - i], mr - i); else hw[i] = 1; while (i - hw[i] >= 0 && i + hw[i] <= n && s[i - hw[i]] == s[i + hw[i]]) hw[i] ++; if (i + hw[i] - 1 > mr) { mr = i + hw[i] - 1; mid = i; } } } int main() { scanf("%s", s + 1); n = strlen(s + 1); manacher(); for (int i = 1; i <= n; ++ i) { //处理出初值 l[i + hw[i] - 1] = max(l[i + hw[i] - 1], hw[i] - 1); r[i - hw[i] + 1] = max(r[i - hw[i] + 1], hw[i] - 1); } for (int i = 0; i <= n; i += 2) r[i] = max(r[i], r[i - 2] - 2); //递推求出l[i]和r[i] for (int i = n; i >= 0; i -= 2) l[i] = max(l[i], l[i + 2] - 2); for (int i = 0; i <= n; i += 2) //注意l[i]和r[i]都不能为0！ if (l[i] && r[i]) ans = max(ans, l[i] + r[i]); printf("%d", ans); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10145787.html
相关资源：JAVA上百实例源码以及开源项目