在一个长度为n的字符串中，找到这个字符串的最长回文长度。
1、n^3做法
枚举回文串的左端点和右端点，从左端点向右端点扫一遍，判断是否是回文。
2、n^2做法
很明显上面的做法浪费了许多判断的时间，若回文串长度是奇数，可以枚举回文串的中点mid，同时向两边扫，找到最长的回文长度，这样可以优化一个n的时间。
若长度是偶数，就找到枚举相邻的两个字符，同时向两边扩展。
3、n做法
那如果n的大小很大，n^2的算法行不通呢？这时就要请manacher出马了。
考虑如何把n^2算法变为n。在枚举回文串的中点时，我们判断了回文串的长度的奇偶性，这样就浪费了时间，且十分麻烦。
所以可以在每个字符串中加上一个原字符串中不会出现的字符（如‘#’），这样就可以将每一个回文串的长度变为奇数。代码如下：
1 void prepare(void) { 2 s[n << 1] = '#'; 3 for (int i = n; i ; -- i) { 4 s[i * 2 - 1] = s[i]; 5 s[i * 2 - 2] = '#'; 6 } 7 n <<= 1; 8 }
可这还是无法将n^2的算法优化成n。会发现，在枚举每个点为中点时，都要向枚举向两边扩展的长度，这样会浪费许多时间，那么如何利用之前的判断快速进行本次的判断呢。
可以记录下maxright表示之前的扩展可以达到的最右边位置，mid表示maxright所对应的回文串的中心，hw[i]表示以i为回文中心所能扩展出去的最长长度（包括i）。
在枚举中点i时，若i < maxright，如下图（mr是maxright，l是maxright关于mid对称的点，j是i点关于mid对称的点）：
因为j点与i点对称，所以i点的hw值应和j点相同。可是若j点的hw值大于了mr - i，那么便不可以直接进行转移（因为这时i与j不再对称），要暴力计算出余下部分是否对称。
若i > maxright，那么就暴力计算hw[i]，后对maxright和mid进行更新。代码如下：
void manacher(void) { prepare(); maxright = 0; mid = 0; ans = 0; for (int i = 0; i <= n; ++ i) { if (i < maxright) { //取出相同的部分 hw[i] = min(hw[mid * 2 - i], maxright - i); } else hw[i] = 1; while (0 <= i - hw[i] && i + hw[i] <= n && s[i + hw[i]] == s[i - hw[i]]) hw[i] ++; //暴力计算hw值 if (i + hw[i] > maxright) { //更新maxright和mid maxright = i + hw[i] - 1; mid = i; } } }
放一道模板题：hdu3068 http://acm.hdu.edu.cn/showproblem.php?pid=3068
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 110005; int hw[maxn << 1],maxright,mid,ans,n; 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(); maxright = 0; mid = 0; ans = 0; for (int i = 0; i <= n; ++ i) { if (i < maxright) { hw[i] = min(hw[mid * 2 - i], maxright - i); } else hw[i] = 1; while (0 <= i - hw[i] && i + hw[i] <= n && s[i + hw[i]] == s[i - hw[i]]) hw[i] ++; if (i + hw[i] - 1 > maxright) { maxright = i + hw[i] - 1; mid = i; } } for (int i = 1; i <= n; ++i) ans = max(ans, hw[i] - 1); } int main() { while (scanf("%s",s + 1) != EOF) { memset(hw, 0, sizeof(hw)); n = strlen(s + 1); manacher(); printf("%d\n", ans); } return 0; }
转载于:https://www.cnblogs.com/Gaxc/p/9874673.html
相关资源：JAVA上百实例源码以及开源项目