給出一個(gè)字符串S，求S的最長(zhǎng)回文子串的長(zhǎng)度。

樣例：字符串“PATZJUJZTACCBCC”的回文子串為“ATZJUJZTA”，長(zhǎng)度為9。

如果使用暴力解法，枚舉子串的兩個(gè)端點(diǎn)i和j，時(shí)間復(fù)雜度需要O(n^2)。判斷子串是否為回文需要O(n)，總體時(shí)間復(fù)雜度為O(n^3)，使用動(dòng)態(tài)規(guī)劃可以達(dá)到最優(yōu)的O(n^3)，而使用動(dòng)態(tài)規(guī)劃解決最長(zhǎng)回文子串的方法有很多種，下面討論最簡(jiǎn)單的一種方法。

令dp[i][j]表示S[i]至S[j]所表示的子串是否為回文子串，是則為1，不是為0。如此根據(jù)S[i]是否等于S[j]，可以把問(wèn)題分為兩類(lèi)：

(1)S[i]==S[j]，那么只要S[i+1]至S[j-1]是回文子串，S[i]至S[j]就是回文子串；如果S[i+1]至S[j-1]是不是回文子串，則S[i]至S[j]也不是回文子串。

(2)S[i]!=S[j]，那么S[i]至S[j]一定不是回文子串。  

由此可以 寫(xiě)出其狀態(tài)轉(zhuǎn)移方程：

邊界：dp[i][i]=1,dp[i][i+1]=(S[i]==S[i+1]?0:1)       ps:這里的dp初始化記錄了長(zhǎng)度為1和2的回文子串

但是這里還存在一個(gè)問(wèn)題，就是在求dp[i][j]時(shí)，無(wú)法保證dp[i+1][j-1]已經(jīng)被計(jì)算了，比如先固定i=0，然后j從2開(kāi)始枚舉。當(dāng)求解dp[0][2]時(shí)，的dp[1][1]已經(jīng)在初始中得到；當(dāng)求解dp[0][3]時(shí)，會(huì)轉(zhuǎn)換求dp[1][2]，而dp[1][2]也在初始化是獲得了；當(dāng)求解dp[0][4]是，轉(zhuǎn)換求解dp[1][3]，但dp[1][3]之前卻沒(méi)有被計(jì)算出來(lái)，因此無(wú)法轉(zhuǎn)移狀態(tài)。

根據(jù)上面的公式，邊界的長(zhǎng)度表示長(zhǎng)度為1和2的回文子串，且每次轉(zhuǎn)移時(shí)都說(shuō)對(duì)子串的長(zhǎng)度減1。因此不妨按照子串的長(zhǎng)度和子串的初始位置進(jìn)行枚舉，即第一次可以枚舉長(zhǎng)度為3的子串的dp值，第二次在第一次的基礎(chǔ)上枚舉長(zhǎng)度為4的子串的dp值....直到枚舉到原字符串的長(zhǎng)度。長(zhǎng)度為3的示意圖如下:

根據(jù)上面的分析，可以給出下面的代碼：

#include <iostream>#include <string>#include <algorithm>using namespace std; const int M=1010;int dp[M][M];  int main(){	int i,j,k,s,e,ans=1; 	string str;	cin>>str;	int len=str.length();	for(i=0;i<len;i++){		dp[i][i]=1;		if(str[i]==str[i+1]){			dp[i][i+1]=1;			ans=2;		}	}	for(k=3;k<=len;k++){ //子串的長(zhǎng)度 		for(i=0;i+k-1<len;i++){ //子串左端點(diǎn) 			j=i+k-1; //子串右端點(diǎn)			if(str[i]==str[j]&&dp[i+1][j-1]){				dp[i][j]=1;				ans=k;				s=i;e=j; //保存最長(zhǎng)回文子串的下標(biāo)			}		} 	}	for(i=s;i<=e;i++){		cout<<str[i]; 	}	cout<<endl<<ans<<endl;	}下面具體看一個(gè)題目：
題目描述        輸入一個(gè)字符串，求出其中最長(zhǎng)的回文子串。子串的含義是：在原串中連續(xù)出現(xiàn)的字符串片段?；匚牡暮x是：正著看和倒著看相同。如abba和yyxyy。在判斷回文時(shí)，應(yīng)該忽略所有標(biāo)點(diǎn)符號(hào)和空格，且忽略大小寫(xiě)，但輸出應(yīng)保持原樣（在回文串的首部和尾部不要輸出多余字符）。輸入字符串長(zhǎng)度不超過(guò)5000，且占據(jù)單獨(dú)的一行。應(yīng)該輸出最長(zhǎng)的回文串，如果有多個(gè)，輸出起始位置最靠左的。輸入一行字符串，字符串長(zhǎng)度不超過(guò)5000。輸出字符串中的最長(zhǎng)回文子串。樣例輸入Confuciuss say:Madam,I'm Adam.樣例輸出Madam,I'm Adam
這個(gè)題目完全可以使用上面的思路來(lái)求解，需要注意的是：上面的方法是求最右端的子串，而題目要求是最左端的子串。解決方法也很容易，從字符串的末端開(kāi)始枚舉即可：
#include <cstdio>#include <cstring>using namespace std; const int M=5002;int dp[M][M];  int pos[M]; //保存新位置到原位置的映射 bool isAlptha(char c){	return 'a'<=c && c<='z' || 'A'<=c && c<='Z';}bool isDigit(char c){	return '0'<=c && c<='9'; }char* toUpper(char* v){	for(int i=0;v[i];i++){		if('a'<=v[i] && v[i]<='z'){			v[i]-=32; 		}	}	return v;}int main(){	int i,j,k,s,e,ans=1,c=0; 	char* str1=new char[M];	char* str=new char[M];	gets(str1);	for(i=0;str1[i];i++){		if(isAlptha(str1[i])||isDigit(str1[i])){			str[c]=str1[i];			pos[c++]=i; //保存新位置到原位置的映射 		}	}	str=toUpper(str);	int len=strlen(str);	for(i=0;i<len;i++){		dp[i][i]=1;		if(str[i]==str[i+1]){			dp[i][i+1]=1;			ans=2;		}	}	for(k=3;k<=len;k++){ //子串的長(zhǎng)度 		for(j=len-1;j-k+1>=0;j--){ 	//子串右端點(diǎn)			i=j-k+1;  //子串左端點(diǎn) 			if(str[i]==str[j]&&dp[i+1][j-1]){				dp[i][j]=1;				ans=k;				s=i;e=j;			}		}	} 	s=pos[s]; e=pos[e]; 	for(i=s;i<=e;i++){		PRintf("%c",str1[i]); 	}	printf("/n");}
題目來(lái)源：http://www.codeup.cn/problem.php?cid=100000629&pid=0