HDU 3068 最長回文 (Manacher算法)

 

最長回文

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 9188 Accepted Submission(s): 3159

 

Problem Description

給出一個只由小寫英文字符a,b,c...y,z組成的字符串S,求S中最長回文串的長度.
回文就是正反讀都是一樣的字符串,如aba, abba等
Input 輸入有多組case,不超過120組,每組輸入為一行小寫英文字符a,b,c...y,z組成的字符串S
兩組case之間由空行隔開(該空行不用處理)
字符串長度len <= 110000
Output 每一行一個整數x,對應一組case,表示該組case的字符串中所包含的最長回文長度.

Sample Input

aaaa

abab

Sample Output

4
3

Source 2009 Multi-University Training Contest 16 - Host by NIT


題目鏈接：www.Bkjia.com

題目分析：manacher算法是用來求解最長回文子串最簡便的算法，下面最這個算法進行簡要介紹：

定義數組p[i]表示以i為中心的(包含i這個字符)回文串半徑長，將字符串s從前往後掃來計算p[i]，最後最大的p[i]就是最長回文串長度，下面闡述如何求解p數組：

由於s是從前往後掃的，所以需要計算p[i]時一定已經計算好了p[1]....p[i - 1]，假設現在掃描到了i + k這個位置，現在需要計算p[i + k]，定義maxp是i + k位置前所有回文串中能延伸到的最右端的位置，maxp = p[i] + i

分兩種情況:

1）i + k這個位置不在前面的任何回文串中，即i + k > maxp，則初始化p[i + k] = 1（即本身是回文串）然後將p[i + k]向左右延伸，

即while(s[i + k + p[i + k]] == s[i + k - p[i + k]]) p[i + k] ++

2）i + k這個位置被前面以位置i為中心的回文串包含，即maxp > i + k，這樣p[i + k]就不從1開始，由回文串的性質可知i + k這個位置關於i與 i - k對稱，所以p[i + k]分為3種情況:

 

1. i - k回文串范圍有一部分在p[i]之外，此時p[i + k] = p[i] - k，此時p[i + k]不可能更長，我們可以反證，假設還有一段d在之後，即

p[i + k] = p[i] - k + d，則根據回文性質可得此時得p[i] = p[i] + d，與p[i]矛盾，故不會更長。

 

2. i - k回文串范圍全部在p[i]以內，此時p[i + k] = p[i - k]，這個很顯然

 

3. i - k回文串范圍剛好等於p[i]，此時p[i + k] = p[i - k]，且可能繼續向左右延伸，

即while(s[i + k + p[i + k]] == s[i + k - p[i + k]]) p[i + k] ++

 

綜合上述所有情況，我們可以得到

p[i + k] = min(p[i - k], p[i] - k)

while(s[i + k + p[i + k]] == s[i + k - p[i + k]])

p[i + k] ++

最後遇到長度為偶數的字符串我們要將其長度變成奇數，穿插未出現的字符即可，防止數組越界，s[0]我們也要設置成一個與''不同的字符

 

#include 
#include 
#include 
using namespace std;
int const MAX = 110005;
char s[MAX << 1];
int p[MAX << 1];

int Manacher()
{
	int len = strlen(s), maxp = 0, ans = 0;
	for(int i = len; i >= 0; i--)
	{
		s[i * 2 + 2] = s[i];
		s[i * 2 + 1] = '#';
	}
	s[0] = '*';
	for(int i = 2; i < 2 * len + 1; i++)
	{
		if(p[maxp] + maxp > i)
			p[i] = min(p[2 * maxp - i], p[maxp] + maxp - i);
		else 
			p[i] = 1;
		while(s[i - p[i]] == s[i + p[i]])
			p[i]++;
		if(p[maxp] + maxp < i + p[i])
			maxp = i;
		if(ans < p[i])
			ans = p[i];
	}
	return ans - 1;
}

int main()
{
	while(scanf(%s, s) != EOF)
		printf(%d
, Manacher());
}