Manacher算法详解：O(n)复杂度求最长回文子串

先预处理下：在每个字符的两边都插入一个特殊的符号，比如abba变成#a#b#b#a#，aba变成 #a#b#a#（因为Manacher算法只能处理奇数长度的字符串）。同时，为了避免数组越界，在字符串开头添加另一特殊符号，比如$#a#b#a#。

以字符串3212343219为例，处理后变成S[] = "$#3#2#1#2#3#4#3#2#1#9#"。
然后用一个数组Len[i]来记录以字符S[i]为中心的最长回文子串的半长度（包括S[i]）：

S   # 3 # 2 # 1 # 2 # 3 # 4 # 3 # 2 # 1 # 9 #
Len 1 2 1 2 1 6 1 2 1 2 1 8 1 2 1 2 1 2 1 2 1

（最终的回文子串的长度即为maxLen-1）

下面两幅图的红框中的字符串为当前的右边界下标最大的回文子串，mid为其中心，right为其最右端+1，i‘=2*mid-i为i关于mid的对称点。

现要计算Len[i]，若以i‘为中心的回文串（黄框）包含在最长回文子串中，则由回文串的对称性，以i为中心的回文串亦在最长回文子串中，即有Len[i]=Len[2*mid-i]

若以i‘为中心的回文串（黄框）不包含在最长回文子串中，则以i为中心的回文串的半长度Len[i]=right-i+(之后继续判断的长度)

那么，为什么复杂度是O(n)的呢？

首先，主要影响复杂度的是s[i + len[i]] == s[i - len[i]]这一判断。

由下面的代码可知，当i<right时，我们就用常数的时间计算Len[i]（此时不会执行while中的语句）；当i>=right时，我们就继续判断：while (s[i + len[i]] == s[i - len[i]]) ++len[i]; 结束后，right < i + len[i]为真，更新right值。这样，我们至多进行n次s[i + len[i]] == s[i - len[i]]判断，故复杂度为O(n)。

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int mx = 10000;

char ss[mx + 5], s[2 * mx + 5];
int len[2 * mx + 5];

void debug()
{
	int i;
	for (i = 1; s[i]; ++i) printf("%c ", s[i]);
	puts("");
	for (i = 1; s[i]; ++i) printf("%d ", len[i]);
	puts("");
}

int main()
{
	int right, mid, i, maxlen;
	while (gets(ss))
	{
		memset(s, 0, sizeof(s));
		s[0] = ‘$‘;
		for (i = 0; ss[i]; ++i) s[2 * i + 1] = ‘#‘, s[2 * i + 2] = ss[i];
		s[2 * i + 1] = ‘#‘;
		memset(len, 0, sizeof(len));
		maxlen = right = mid = 0;
		for (i = 1; s[i]; ++i)
		{
			len[i] = (i < right ? min(len[(mid << 1) - i], right - i) : 1);
			/* 取min的原因：记点i关于mid的对称点为i‘，
			若以i‘为中心的回文串范围超过了以mid为中心的回文串的范围
			(此时有i + len[(mid << 1) - i] >= right，注意len是包括中心的半长度)
			则len[i]应取right - i(总不能超过边界吧) */
			while (s[i + len[i]] == s[i - len[i]]) ++len[i];
			maxlen = max(maxlen, len[i]);
			if (right < i + len[i]) mid = i, right = i + len[i]; 
		}
		printf("%d\n", maxlen - 1);
		debug();
	}
	return 0;
}

例题：

HDU 3068 最长回文

POJ 3974 Palindrome

Manacher算法详解：O(n)复杂度求最长回文子串

原文：http://blog.csdn.net/synapse7/article/details/18908413