题目：最长回文子串
笔记 1#
参考了这里的解法：https://leetcode.cn/problems/longest-palindromic-substring/solutions/2958179/mo-ban-on-manacher-suan-fa-pythonjavacgo-t6cx/
对于奇回文串，我们从最中间的一个元素开始向两边扩散，比如“bab”，第一次判断时 left = right，条件符合，所以 left–， right++；然后进入第二次判断，此时两者指向的字符都是‘b’，条件依然满足….直到左右指针指向的字符不同时，计算当前字符串长度
对于偶回文串，还是从中间开始扩散，只不过这次需要选取两个元素
为了将两种情况合并处理，可以将 i 的最大范围改为 2n - 1，因为
1string longestPalindrome(string s)
2{
3 int left = 0, right = 0;
4 int n = s.size();
5 for(int i = 0; i < 2 * n - 1; i++)
6 {
7 int l = i / 2, r = (i + 1) / 2;
8 while(0 <= l && r < n && s[l] == s[r])
9 {
10 l--;
11 r++;
12 }
13 if(r - l - 1 > right - left)
14 {
15 right = r;
16 left = l + 1;
17 }
18 }
19 return s.substr(left, right - left);
20}
来源：语雀原笔记
笔记 2#
以一个字符（奇数回文串）或两个字符中间的空隙（偶数回文串）为中心，向左右两端扩散，如果两端字符相同，则继续扩展，并记录当前字符串的起始点
1std::pair<int, int> ExpandAroundCenter(const string& s, int left, int right)
2{
3 while(left >= 0 && right < s.size() && s[left] == s[right])
4 {
5 --left;
6 ++right;
7 }
8 return {left+1, right-1};
9}
10string longestPalindrome(string s)
11{
12 int left = 0, right = 0;
13 // 如果输入字符串总长为1，则直接返回该字符串
14 if(s.size() < 2)
15 return s;
16 for(int i = 0; i < s.size(); ++i)
17 {
18 // 奇数回文串
19 auto [left1, right1] = ExpandAroundCenter(s, i, i);
20 // 偶数回文串
21 auto [left2, right2] = ExpandAroundCenter(s, i, i+1);
22 // 判断是奇数还是偶数
23 if(right1 - left1 > right - left)
24 {
25 left = left1;
26 right = right1;
27 }
28 if(right2 - left2 > right - left)
29 {
30 left = left2;
31 right = right2;
32 }
33 }
34 // substr（start，length）：提取特定字符串
35 return s.substr(left, right-left+1);
36}
来源：语雀原笔记