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.
动态规划解法 O（n2) 超时
string longestPalindrome(string s) {
if(s.empty()) return s;
vector<vector<bool>> isPalindrome(s.length() + , vector<bool>(s.length() + , false));
string ans = s.substr(,);
for(int i = ; i <= s.length(); i++) //长度
{
for(int j = ; j <= s.length() - i; j++) //起始位置
{
if((i <= ) || (isPalindrome[j + ][i - ] && s[j] == s[j + i - ]))
{
isPalindrome[j][i] = true;
if(i > ans.length())
ans = s.substr(j, i);
}
}
}
return ans;
}
O(N)解法 AC
string longestPalindrome2(string s)
{
if(s.empty()) return s;
string ss = "#";
for(int i = ; i < s.length(); i++)
{
ss += s.substr(i, ) + "#";
}
vector<int> P(ss.length()); //记录新字符串以每一个字符为中心时 包括中心的一半长度 只有一个时长度为1
string ans = s.substr(,);
int mx = ; //向右最远的对称位置+1
int id = ; //mx对应的中心位置
for(int i = ; i < ss.length(); i++)
{
P[i] = (mx > i) ? min(P[*id - i], mx - i) : ;
while(i - P[i] >= && i + P[i] < ss.length() && ss[i - P[i]] == ss[i + P[i]]) P[i]++;
if(P[i] - > ans.length())
ans = s.substr((i - P[i] + )/, P[i] - );
if(i + P[i] > mx)
{
mx = i + P[i];
id = i;
}
}
return ans;
}