字符串最長回文子串
題目描述：
給定一個字符串，求它的最長回文子串的長度。
分析和解法：
最容易想到的辦法是枚舉所有的子串，分別判斷其是否為回文，然后在其中找出最長的。這個思路初看起來是正確的，但卻做了很多無用功，如果一個長的子串包含另一個短一些的子串，那么對子串的回文判斷其實是不需要的。而且如果找到了長的回文子串，比它短的就不用看了。
解法一：枚舉中心
那么如何高效的進行判斷呢？我們想想，如果一段字符串是回文，那么以某個字符為中心的前綴和后綴都是相同的，例如以一段回文串“aba”為例，以b為中心，它的前綴和后綴都是相同的，都是a。
那么，我們是否可以可以枚舉中心位置，然后再在該位置上用擴展法，記錄并更新得到的最長的回文長度呢？答案是肯定的。
源代碼如下：
#include <iostream>
#include <cstring>
using namespace std;
int LongestPalindrome(char *s, int n)
{
int i, j, max, c;
if(s == 0 || n < 1)
return 0;
max = 0;
for(i = 0; i < n; ++i) //i是回文子串的中點
{
if(n % 2 == 1) //回文子串的長度為奇數(shù)
{
for(j = 0; (i - j >= 0) && (i + j < n); ++j)
{
if(s[i - j] != s[i + j])
break;
c = j * 2 + 1;
}
}
else //回文子串的長度為偶數(shù)
{
for(j = 0; (i - j >= 0) && (i +j + 1 < n); ++j)
{
if(s[i - j] != s[i + j + 1])
break;
c = j * 2 + 2;
}
}
if(c > max)
max = c;
}
return max;
}
int main()
{
char str[100];
cin >> str;
cout << LongestPalindrome(str, strlen(str));
return 0;
}
分析：上面的代碼是對全部情況進行了遍歷，當然，我們還可以稍加改善一下，max的初始值可以設置為1，因為前面已經(jīng)處理了字符串為空的情況，所以但凡有正確輸入，一個字符也算是一個回文子串，所以最小的長度為1，i 的取值范圍可以從1到n - 1，j 的初始值可以從1開始。
解法二：Manacher算法
在上文的解法一：枚舉中心位置中，我們需要特別考慮字符串的長度是奇數(shù)還是偶數(shù)，所以導致我們在編寫代碼實現(xiàn)的時候要把奇數(shù)和偶數(shù)的情況分開編寫，是否有一種方法，可以不用管長度是奇數(shù)還是偶數(shù)，而統(tǒng)一處理呢？比如是否能把所有的情況全部轉(zhuǎn)換為奇數(shù)處理？
答案還是肯定的。這就是下面我們將要看到的Manacher算法，且這個算法求最長回文子串的時間復雜度是線性O(N)的。
首先通過在每個字符的兩邊都插入一個特殊的符號，將所有可能的奇數(shù)或偶數(shù)長度的回文子串都轉(zhuǎn)換成了奇數(shù)長度。比如 abba 變成 #a#b#b#a#， aba變成 #a#b#a#。
此外，為了進一步減少編碼的復雜度，可以在字符串的開始加入另一個特殊字符，這樣就不用特殊處理越界問題，比如$#a#b#a#。
以字符串12212321為例，插入#和$這兩個特殊符號，變成了 S[] = "$#1#2#2#1#2#3#2#1#"，然后用一個數(shù)組 P[i] 來記錄以字符S[i]為中心的最長回文子串向左或向右擴張的長度（包括S[i]）。
比如S和P的對應關系：
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
可以看出，P[i]-1正好是原字符串中回文串的總長度
那么怎么計算P[i]呢？該算法增加兩個輔助變量（其實一個就夠了，兩個更清晰）id和mx，其中 id 為已知的右邊界最大的回文子串的中心，mx則為id+P[id]，也就是這個子串的右邊界。
然后可以得到一個非常神奇的結論，這個算法的關鍵點就在這里了：
如果mx > i，那么P[i] >= Min(P[2 * id - i], mx - i)
就是這個結論卡了我非常久。實際上如果把它寫得復雜一點，理解起來會簡單很多：
//記j = 2 * id - i，也就是說 j 是 i 關于 id 的對稱點(j = id - (i - id))
if (mx - i > P[j])
P[i] = P[j];
else /* P[j] >= mx - i */
P[i] = mx - i; // P[i] >= mx - i，取最小值，之后再匹配更新。
當然光看代碼還是不夠清晰，還是借助圖來理解比較容易。
當 mx - i > P[j] 的時候，以S[j]為中心的回文子串包含在以S[id]為中心的回文子串中，由于i和j對稱，以S[i]為中心的回文子串必然包含在以S[id]為中心的回文子串中，所以必有P[i] = P[j]；
當 P[j] >= mx - i 的時候，以S[j]為中心的回文子串不一定完全包含于以S[id]為中心的回文子串中，但是基于對稱性可知，下圖中兩個綠框所包圍的部分是相同的，也就是說以S[i]為中心的回文子串，其向右至少會擴張到mx的位置，也就是說 P[i] >= mx - i。至于mx之后的部分是否對稱，再具體匹配。
此外，對于 mx <= i 的情況，因為無法對 P[i]做更多的假設，只能讓P[i] = 1，然后再去匹配。
源代碼如下：
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
void findBMstr(string& str)
{
int *p = new int[str.size() + 1];
memset(p, 0, sizeof(p));
int mx = 0, id = 0;
for(int i = 1; i <= str.size(); i++)
{
if(mx > i)
{
int j = 2 * id - i;
p[i] = (p[j] < (mx - i) ? p[j] : (mx - i));
}
else
{
p[i] = 1;
}
while(i + p[i] < str.size() && str[i - p[i]] == str[i + p[i]])
p[i]++;
if(i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
int max = 0, ii;
for(int i = 1; i < str.size(); i++)
{
if(p[i] > max)
{
ii = i;
max = p[i];
}
}
max--;
cout << max <<endl;
int start = ii - max ;
int end = ii + max;
for(int i = start; i <= end; i++)
{
if(str[i] != '#')
{
cout << str[i];
}
}
cout << endl;
delete p;
}
int main()
{
string str;
cin >> str;
string str0;
str0 += "$#";
for(int i = 0; i < str.size(); i++)
{
str0 += str[i];
str0 += "#";
}
cout << str0 << endl;
findBMstr(str0);
return 0;
}
分析：Manacher算法使用id、mx做配合，可以在每次循環(huán)中，直接對P[i]的快速賦值，從而在計算以i為中心的回文子串的過程中，不必每次都從1開始比較，減少了比較次數(shù)，最終使得求解最長回文子串的長度達到線性O(N)的時間復雜度。
特別注意：
- 解法二挺繞的，不是很好理解，建議對照圖例細細品味
參考資料：《編程之法》The Art of Programming By July
