我現(xiàn)在在做一個(gè)叫《leetbook》的開源書項(xiàng)目危队，把解題思路都同步更新到github上了奢驯，需要的同學(xué)可以去看看
地址：https://github.com/hk029/leetcode
這個(gè)是書的地址：https://hk029.gitbooks.io/leetbook/
這里寫圖片描述
005.Longest Palindromic [M]
題目
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.
思路
可以用的算法有改良KMP還有manacher（馬拉車）算法话肖，毫無(wú)疑問(wèn)剥纷，manacher算法是專門用來(lái)解決最長(zhǎng)子串問(wèn)題的抒钱，也是最簡(jiǎn)便的翘魄。關(guān)于這個(gè)算法可以看: Manacher算法
class Solution {
public:
string longestPalindrome(string s) {
//manacher
int bound = 0;
int id,max_pos=0;
int new_len = 2*s.length()+2;
vector<int> P(new_len,1);
string new_str(new_len-1,'#');
//生成新串鼎天，把所有的字符串通過(guò)’#’擴(kuò)展成奇數(shù)
for(int i = 0;i < s.length();i++)
{
new_str[2*i+1] = s[i];
}
new_str = '$'+new_str +='\0'; //防止越界
//manacher算法
for(int i=1;i < new_len; i++)
{
if(i < bound)
{
P[i] = min(bound-i,P[2*id-i]); //如果在范圍內(nèi)，找對(duì)稱面的P[id-(i-id)]和max_pos-i的最小值
}
while(new_str[i-P[i]] == new_str[i+P[i]])//查找以這個(gè)字符為中心的回文串
{
P[i]++;
}
//更新id和bound
if(i+P[i] > bound)
{
bound = i+P[i];
id = i;
}
max_pos = P[i] > P[max_pos]?i:max_pos;
}
int len = P[max_pos]-1;
int start = (max_pos-P[max_pos])/2;
return s.substr(start,len);
}
};
