1. 建立長度為2*s.size()+1的字元串str, 在str奇數位指派為#, 偶數位str[i] = s[i/2] —— 亦即在字元串s的兩邊及相鄰字元間加上#.
這樣的好處是不用考慮最長回文長度是奇數還是偶數的情況。在str中標明中心,對比兩邊即可:
若最長回文長度為偶數,那麼那個中心将是我們額外插入的某個#;
若為奇數,中心仍為未擴充前的s的最長回文子串中心。
2. 可采用manacher算法 (O(n)求最長回文子串)
代碼:
class Solution
{
public:
string longestPalindrome(string s)
{
string str(2*s.size()+1, 0);
// str
for (size_t i = 0, j = 0; i < str.size(); ++ i)
{
if (i % 2 == 0)
{
str[i] = 0;
} else
{
str[i] = s[j ++];
}
}
// p
int mx = 0, id, max_length=0, max_id;
vector<int> p(2*s.size()+1, 0);
for (int i = 0; i < str.size(); ++ i)
{
p[i] = mx>i? min(p[2*id-i], mx-i): 0;
for ( ; i-p[i]-1>=0 && i+p[i]+1<str.size()
&& str[i-p[i]-1] == str[i+p[i]+1]; ++ p[i]) {}
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
if (max_length < p[i])
{
max_length = p[i];
max_id = i;
}
}
return s.substr((max_id-p[max_id])/2, p[max_id]);
}
};