首页 > 代码库 > HDU - 3068 最长回文（manacher算法）
HDU - 3068 最长回文（manacher算法）
题意：给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
分析：
manacher算法：
1、将字符串中每个字符的两边都插入一个特殊字符。（此操作的目的是，将字符串长度统一变成奇数，道理很容易想---奇数+偶数=奇数or偶数+奇数=奇数）
eg：abba--->#a#b#b#a#
此外，为了便于处理边界，可在字符串开始处再加另外一个特殊字符。
eg：#a#b#b#a#--->$#a#b#b#a#
2、数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度，显然，P[i]-1正好是原字符串中以字符S[i]为中心的回文串长度。
3、计算P[i]。
id---已知的 右边界最大 的回文子串ss的中心
ma---id+P[id]，子串ss的右边界
j--- i 关于 id 的对称点，因此j=id * 2 - i
（1）如果ma > i，则
（i）若p[j] < ma - i, 则p[i] = p[j]。
原因：因为以id为中心是个大的回文串，若已知 在位置id左侧的回文串内 有 某点j ，且以点j为中心有个长度为p[j]（p[j]是小于ma-i的）的回文串，那么 以点i（i是j关于id的对称点，i在id右侧且因为对称，所以一定在回文串内）为中心一定有一个回文串，且该回文串长度为p[j]。
（ii）若p[j] >= ma - i, 则p[i] = ma - i。
原因：因为以id为中心的大的回文串右边界只延伸到ma，根据对称性，虽然p[j]大于ma-i，但是，对于以点i为中心的回文串，只能知道右边界为ma-i的范围内一定是个回文串，再往右情况未知，只能左右延伸依次判断。
（2）如果ma <= i，只能左右延伸依次判断。
#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<cmath>#include<iostream>#include<sstream>#include<iterator>#include<algorithm>#include<string>#include<vector>#include<set>#include<map>#include<stack>#include<deque>#include<queue>#include<list>#define lowbit(x) (x & (-x))const double eps = 1e-8;inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1;}typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const int MAXN = 110000 + 10;const int MAXT = 10000 + 10;using namespace std;char s[MAXN];int p[MAXN << 1];char t[MAXN << 1];int len;int cnt;void init(){ memset(t, 0, sizeof t); cnt = 0; t[cnt++] = ‘$‘; for(int i = 0; i < len; ++i){ t[cnt++] = ‘#‘; t[cnt++] = s[i]; } t[cnt++] = ‘#‘;}int manacher(){ int ma = 0, id = 0, ans = 1; for(int i = 1; i < cnt; ++i){ p[i] = ma > i ? min(p[id * 2 - i], ma - i) : 1; while(t[i + p[i]] == t[i - p[i]]) ++p[i]; if(i + p[i] > ma){ ma = i + p[i]; id = i; } ans = max(ans, p[i]); } return ans - 1;}int main(){ while(scanf("%s", s) == 1){ len = strlen(s); init(); printf("%d\n", manacher()); } return 0;}
HDU - 3068 最长回文（manacher算法）