poj3974 Palindrome [字元串回文]

本題的題意是給你一個字元串 讓你判斷這個字元串中最長的回文子串的長度

嗯 這題可以用O（n）的時間複雜度的manacher算法來處理

manacher在很久前就知道了，但是隻是知道了怎麼去構造但是還沒沒有明白怎麼去更新

嗯 大概就是這樣的情況 嗯是以 看了人家的部落格點選打開連結 寫的非常的明白

首先我們先在原來的字元串中插入不用到的字元形如  abcd -> #a#b#c#d#

這樣做了之後就可以将奇數個長的回文串和偶數長的回文串整合起來了

主要考慮怎麼去計算dp[i]（dp[i] 表示以i為中心的字元串能構成多長的回文串）

考慮下面兩種情況

1）i 不在以i之前的點為中心的回文串所包含

那麼就需要哦從i開始向外判斷回文

2）i在之前的點位中心的回文串所包含 假設這個中心點為l k為i-l

那麼更具回文串的性質 l+k（i）位置的點 和 l-k的位置 的情況一樣的

在2）的條件下會有上述的三種情況

情況一：這種情況比較的簡單 dp[i]=dp[l-k];

情況二：這種情況要想明白 很顯然不可能在i處出現對應到最長的回文串外的如果能夠出去表示最長回文串的長度仍能增加 這和我們的定義不符

是以在情況二中的dp[i]=dp[l]+l-i;

情況三就是說我們i對應的位置能夠擴充到最長回文串的邊緣 這個時候我們就需要繼續的向外擴充找能否有更長的回文串

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
char s[2000100];
int dp[2000100];
int main(){
	int cas=1;
	while(~scanf("%s",&s)){
		if(s[0]=='E') break;
		int len=strlen(s);
		for(int i=len;i>=0;i--){
			s[i+i+2]=s[i];
			s[i+i+1]='#';
		}
		s[0]='.';
		len=strlen(s);
		int l=0,ans=0;
		dp[0]=1;
		for(int i=1;i<len;i++){
			if(l+dp[l]<=i){
				dp[i]=1;
				int k=1;
				while(s[i+k]==s[i-k]) k++,dp[i]++;
			}else{
				int k=i-l;
				dp[i]=dp[l-k];
				if(i+dp[i]>l+dp[l])dp[i]=dp[l]+l-i;
				k=dp[i];
				while(s[i+k]==s[i-k]) k++,dp[i]++;
			}
			if(l+dp[l]<i+dp[i])  l=i;
			ans=max(ans,dp[i]-1);		
		}
		printf("Case %d: %d\n",cas++,ans);
	//	printf("%d\n",ans);
	}
}