最長回文字串（Longest Palindromic Substring）
題目：Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
題目連接配接：https://leetcode.com/problems/longest-palindromic-substring/
大意是給定一個字元串S，求S中最長的回文字串，回文字元串是指從坐到右和從右到左都是一樣的字元串，例如：“西湖回遊魚遊回湖西”、“ABDCDBA”、“abccba”等等諸如此類的字元串，單個字元的串，也是回文串。
思路1：暴力解法，枚舉S的所有字串，判斷每個字元串是否是回文串，傳回最長的串，當字元串很長的時候，枚舉也隻能想想了，更别說還要判斷是否是回文。 思路2：枚舉中心法，我們感興趣的隻是串中的回文字串，因為回文串的性質，那麼我們可以枚舉串中每一個字元，來檢查以它為中心的串是不是回文串，并選取其中最長的傳回。 例如： ABDCDBA 1.以A為中心，A的左邊沒有字元，是以隻能是A當作一個回文。 2.以B為中心，那麼比較B的左邊和右邊字元是否相等。相等，是回文。否則，不是。 3.以此類推，直到所有的字元作為中心判斷完。 假設以i為中心，j為i左右的長度，且滿足條件1：(i-j)>=0 && (i+j)<S.size(); j從0開始，到不能滿足條件1結 束，分别判斷，判斷完成以i為中心後，以i+1為中心再進行類似判斷。當然還有一個問題，就是回文串的長度有 可能是奇數，也可能是偶數。例如ABA、ABBA都是回文。這個時候隻需要對奇數還是偶數進行分别判斷： 奇數時：判斷S[i-j] == S[i+j]，j滿足(i-j)>=0 && (i+j)<S.size()。 偶數使：判斷S[i-j] == S[i+j+1]，j滿足(i-j)>=0 && (i+j+1)<S.size() CODE:
string LongestPalindrome( string s)
{
int start=0,maxLen = 1,tlen = 1,ti=0;
int size = s.size();
if( size <= 1 )
return s;
// 奇數
for( int i = 0; i < size; i++)
{
for( int j = 0; (i-j>=0) && (i+j
= maxlen )
{
maxlen = tlen;
start = i-j;
}
// 偶數
for( int j = 0; (i-j>=0) && (i+j+1 <= n); ++j )
{
if( s[i-j] != s[i+j+1])
break;
tlen = 2*j+2;
ti = i-j;
}
if(tlen > maxlen )
{
maxlen = tlen;
start = ti;
}
}
return s.substr(start,maxlen);
}
思路3：先看下面的例子： A AABABBAABCBABC .... 可以看出什麼？ A按規定是一個回文，要判斷BAB是不是回文，那麼判斷B==B，且A是不是回文。判斷BAAB，則判斷B==B? 且AA是不是回文。以此類推，可以總結 到： 1.單個字元是回文。 2.兩個字元相同是回文，否則不是。 3.長度大于等于3的串，滿足s[0]==s[s.size-1] && s.substr(1,s.size-2)是不是回文。滿足則是，否則不是。 更一般化來講： 對于以i為起點，j為長度的string是不是回文串，隻需要判斷，s[i]==s[s+j-1]且s[i+1 to i+j-2]之間的串是不是回文串，這樣問題規模就減小了，對于規模 大的問題轉換到小規模問題求解，那麼很容易想到的就是動态規劃。 DP[i][i] = true; i<s.size(); DP[i][i+1] = true； if( s[i]==s[i+1] && i<s.size()-1) DP[i][j] = true; if( s[i]==s[j] && DP[i+1][j-1] && i<size & j < size) 按照這個思路很自然可以得出代碼： CODE
string longestPalindrome(string s) {
const int size = s.size();
if( size == 1)
return s;
bool dp[1000][1000] ;
for( int i = 0; i < 1000; i++)
memset(dp[i],false,1000);
int maxlen =1;
int start = 0;
for( int i = 0; i < 1000; i++)
{
dp[i][i]= true;
if( i<(size-1) && (s[i] == s[i+1]))
{
dp[i][i+1]=true;
start = i;
maxlen = 2;
}
}
for( int len = 3; len <= size; len++)
{
for(int i = 0; i < size-len+1; i++)
{
int j = i+len-1;
if( dp[i+1][j-1] && (s.at(i)==s.at(j)))
{
dp[i][j] = true;
start = i;
maxlen = len;
}
}
}
if( maxlen >= 2)
{
return s.substr(start,maxlen);
}
return NULL;
}
抛開暴力枚舉的方法，因為效率太低了，中心枚舉和動态規劃的時間複雜度都是O(n^2),還有沒有更高效的方法呢？當然有，這就是傳說中的Manacher算法，這個方法需要點想象力啊。
思路4：Manacher算法，這就是個傳說。 Manacher算法思想是來自上述“中心擴充法”，在“中心法”中要考慮回文 串是奇數還是偶數，有沒辦法統一處理呢？有，這就是Manacher算法。 該算法首先将字元串的每個字元之間加入一個特殊字元，并且在字元串開頭加入一個标志來更好處理越界和編碼問題。例如：s=“abba”編碼後是：s=“$#a#b#b#a#”。 然後，用一個數組p來記錄每個字元是s[i]為中心的的回文串向左或向右的長度，則原字元串s的回文長度為max(p[i]-1)。因為對于一個回文字元串s加入特殊字元後，該回文串加上特殊字元後依然會是一個回文串，且編碼後的回文串的長度為2*s.size+1。那麼數組記錄的最大值為s.size+1，比原回文的長度多1。故求取p[]的最大值減1就是原字元串中最大的回文串。 現在最重要的問題就是怎麼求解p[],這似乎又回到原來開始的問題了，非也。因為加了特殊字元，會出現一些有用的結論。 假設現在求p[i]的值，則p[0]...p[i-1]的值已經求出，maxlen為目前已經求出的回文串延伸到右邊的最大長度，id為p[0]到p[i-1]最大回文串的中心，j為i關于id的對稱點，即j=2*id-i。那麼： 1.如果i不在maxlen範圍内，即不在任何回文串中,則p[i]=1（本身為回文）。接着判斷p[i+j]==p[i-j]，為真則++p[i]，否則2； 2.p[i]>=min(p[2id-i],maxlen-i]。
證明： 情況1：
情況2：
情況3：
int Manacher(string s)
{
int len = s.size();
int maxLen = 0;
int id;
int mx = 0;
for (int i = 1; i < len; i++)
{
if (i < maxLen)
p[i] = min(p[2 * id - i], maxLen - i);
else
p[i] = 1;
while (s_new[i - p[i]] == s_new[i + p[i]])
p[i]++;
if (maxLen < i + p[i])
{
id = i;
maxLen = i + p[i];
}
mx = max(mx, p[i] - 1);
}
return mx;
}