线性时间求解最大回文字串

这道题源于华为校园招聘的机试题，想了很久没有好的解法，google之后发现Manacher's Algorithm可以达到O(n)的复杂度。

这篇文章讲得比较详细：http://www.felix021.com/blog/read.php?2040

C代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 1000000

int min(int a, int b)
{
        int result;
	result = a > b ? b : a;
	return result;
}

int main()
{
	char input[MAXSIZE], str[MAXSIZE];
	char *result;
	int p[MAXSIZE];
	int i, j;
	int mx, id;
	int maxlen;
	int pos;
	
	str[0] = '$';
	str[1] = '#';
	while(gets(input))
	{
		memset(p, 0, sizeof(p));
		mx = 0;
		id = 0;
		j = 2;
		for(i=0; i<strlen(input); i++)
		{
			
			str[j] = input[i];
			j++;
			str[j] = '#';
			j++;
		}
		str[j] = '\0';
		
		for(i=1; i<strlen(str); i++)
		{
			p[i] = mx > i ? min(str[2*id-1], mx-i) : 1;
			while(str[i+p[i]] == str[i-p[i]])
				p[i]++;
			if(i+p[i] > mx)
			{
				mx = i + p[i];
				id = i;
			}
		}
		
		maxlen = 0;
		pos = 0;
		for(i=1; i<strlen(str); i++)
			if(p[i] > maxlen)
			{
				maxlen = p[i];
				pos = i;
			}
		
		result = (char*) malloc(sizeof(char)*(maxlen));
		j = 0;
		for(i=pos-(maxlen-1); i<=pos+(maxlen-1); i++)
		{
			if(str[i] != '#')
			{
				result[j] = str[i];
				j++;
			}
		}
		result[j] = '\0';
		
		printf("length of the longest palindrome is %d\n", maxlen-1);
		printf("Palindrome is %s\n", result);	
	}
	return 0;
}

总结:

1. 在字符串中插入'#', 将奇数与偶数长度的回文串统一考虑

2. 使用数组记录已求回文的最右边界，降低时间复杂度到O(n)