算法与数据结构最长回文子串
目录
算法与数据结构（最长回文子串）
题目
思路
这个题可以用中心扩展法。遍历每个可能的中心点，然后向两边扩展，记录最长的回文子串。这样可以覆盖所有可能的奇数长度和偶数长度的回文情况。
首先可以写一个扩展函数，返回值的类型为pair<int,int>。
若left和right在字符串s的范围内且s[left] == s[right]则扩展一位(left–,right++)。
最后返回满足条件的子串的范围。
auto [left1,right1] = expand(s,i,i);
auto [left2,right2] = expand(s,i,i+1);这个是用来求两种情况：子串长度为1，子串长度为2。
若比end-start的长度长，则更新start和end的值。
return s.substr(start,end-start+1);这个函数是用来求s字符串从位置start开始，长度为end-start+1的子串。
代码
class Solution {
public:
pair<int,int> expand(string s, int left, int right)
{
//从中间向两边扩展
while(left >= 0 && right < s.size() && s[left] == s[right])
{
left--;
right++;
}
return {left+1,right-1};
}
string longestPalindrome(string s)
{
int start=0,end=0;
for(int i=0; i<s.size();i++)
{
auto [left1,right1] = expand(s,i,i);
auto [left2,right2] = expand(s,i,i+1);
if(right1 - left1 > end - start)
{
start = left1;
end = right1;
}
if(right2 - left2 > end - start)
{
start = left2;
end = right2;
}
}
return s.substr(start,end-start+1);
}
};