我之前竟然没有记这道题……奇怪了嘿……
问题描述
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"
问题分析
有成熟的算法来解这个问题：Manacher's Algorithm 马拉车算法
核心思想是，记录当前回文已经到达的最右边的边界，若新位置在边界内，则可以利用回文的对称性，减少计算。
AC代码
class Solution {
public:
int min(int a, int b){
if (a < b)
return a;
else
return b;
}
string preprocessing(string s){
int len = s.size();
string rst = "^#";
for (auto c: s){
rst += c;
rst += '#';
}
rst += '$';
return rst;
}
string longestPalindrome(string s) {
string rst = preprocessing(s);
vector<int> p(rst.size(), 1);
int center = 1;
int brim = 1;
int max = 1;
for (int i = 2; i < rst.size(); i++){
int t = i < brim ? min(p[2 * center - i], brim - i) : 1;
int j1 = i + t;
int j2 = i - t;
while (rst[j1] == rst[j2]){
t++;
j1++;
j2--;
}
p[i] = t;
if (t > p[max]){
max = i;
}
if (i + t > brim){
center = i;
brim = i + t;
}
}
string r = rst.substr(2 * max - (max + p[max] - 1), 2 * p[max] - 1);
for (auto it = r.begin(); it != r.end();){
if (*it == '#' || *it == '^' || *it == '$')
it=r.erase(it);
else
it++;
}
return r;
}
};
Runtime: 6 ms, which beats 76.09% of cpp submissions.
