马拉车算法板子
#算法
求字符串最长回文子串 马拉车算法
时间复杂度O(N)，算法核心：充分利用回文串对称的特性，作出当前字符中心扩展的结果或最小估计，减少中心扩展次数，实质是对中心扩展算法的极致优化
string mlc(string str) {
string s = "$#";
for (auto c : str) {
s += c;
s += "#";
}
s += "^";
//中间插空无关字符，无需判断奇偶
int max_c = 0;//最长回文子串的中心
int max_len = 0;//最长回文子串的长度
int r = 0;//翼展最靠右的位置
int c = 0;//翼展最靠右的中心
int len = s.size();
vector<int>p(len);//以p[i]为中心，向两边可以扩展的次数
for (int i = 1;i <= len - 2;i++) {//有效字符1~len-2
int j = 2 * c - i;//i关于最大蘑菇的对称位置
if (i <= r)p[i] = min(p[j], r - i);
while (s[i - p[i] - 1] == s[i + p[i] + 1])p[i]++;//中心扩展算法
if (p[i] > max_len) {//更新最长回文子串
max_len = p[i];
max_c = i;
}
if (i + p[i] > r) {//更新翼展最靠右的位置和中心
r = i + p[i];
c = i;
}
}
string res;
for (int i = max_c - max_len + 1;i < max_c + max_len;i++) {
if (s[i] != '#')res += s[i];
}
return res;//返回最长回文子串
}