Manacher算法
马拉车算法
最长回文子串的朴素解法
回文串:如果一个长度为n的字符串
s
为回文串,n
可为奇数或偶数,对应两种情况:
n
为奇数时,回文中心为C
, 回文半径为R
:
n
为偶数时,回文中心为,回文半径为R
:
string preProcess(const string& s) {
string ret = "^";
for (auto ch: s) {
ret += '#';
ret += ch;
}
ret += "#$";
return ret;
}
string longestPalindrome(string s) {
string sx = preProcess(s);
int n = sx.size();
vector<int> P(n);
int C = 0, R = 0;
for (int i = 1; i < n-1; ++i) {
int mirror_i = 2 * C - i;
if (R > i) P[i] = min(P[mirror_i], R - i);
while (sx[i-P[i]-1] == sx[i+P[i]+1]) ++P[i];
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
int max_len = 0, max_id = 0;
for (int i = 1; i < n - 1; ++i) {
if (P[i] > max_len) {
max_len = P[i];
max_id = i;
}
}
int st = (max_id - max_len) >> 1;
return s.substr(st, max_len);
}
Manacher算法
http://example.com/2022/07/15/Manacher/