问题
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
思路
最长回文子串，很经典的题。
思路一：自己想的话就是枚举字符串的中心，然后判断，时间复杂度O(n^2)。
思路二：Manacher算法，时间复杂度O(n)。
参考 https://segmentfault.com/a/1190000003914228
实现
class Solution {
public:
string longestPalindrome(string s) {
const int MAX_STR = 1005;
string str;
for(int i=0; i<s.size(); i++){
str.append("#");
str.append(s, i, 1);
}
str.append("#");
int pos=0, MaxRight=0, RL[MAX_STR*2+1]={0};
for(int i=0; i<str.size(); i++){
int j;
if(i<MaxRight){
j=min(RL[2*pos-i], MaxRight-i);
}
else{
j=1;
}
while(i+j<str.size() && i-j>=0 && str[i-j]==str[i+j]){
j++;
}
RL[i]=j;
if(i+j-1>MaxRight){
pos = i;
MaxRight = i+j-1;
}
}
int maxi=0, maxRL=0;
for(int i=0; i<str.size(); i++){
if(RL[i]>maxRL){
maxRL = RL[i];
maxi = i;
}
}
return s.substr((maxi-maxRL+1)/2, maxRL-1);
}
};
思考
主要是学习Manacher算法
并且熟悉string的相关操作
