马拉车(Manacher)
马拉车算法(Manacher)是一种常见的字符串算法。下面我就来讲一讲。
1.简介
Manacher算法是一种快速判断字符串最长回文长度的一种字符串算法，分为三个步骤：预处理、加速盒子和主算法。
2.代码
1.预处理
string b = "@";
char a[200005];
int n, r, m, ans, d[200005];
void pre(){
for (ll i = 0; i < n; i++){
b += '#';
b += a[i];
}
b+='#';
//如果字符串是"asda"，那么处理后的字符串就是"@#a#s#d#a#"，为以后的算法做准备。
}
2.加速盒子(提示：这是以中间m长度为基准，还有一种方法是以右侧为基准，欢迎大家在评论区写出另一种的加速盒子)
void fast_box(int pos){
//重点：利用以前的回文长度和自己的回文长度比较，比谁小
d[pos] = min(d[2*m-pos], r-pos+1);
}
3.主算法
void Manacher(){
for (int i = 1; i < b.size(); i++){
if (i <= r) fast_box(i);
}
//暴力枚举
while (b[i - d[i]] == b[i + d[i]]) d[i]++;
//更新答案
if (i + d[i] >= r){
m = i;
r = i + d[i] - 1;
ans = max(ans, d[i]-1);
}
cout << ans << endl;
}
这就是Manacher的全部了，点个赞再走呗。在main函数直接调用pre()函数和Manacher()函数就行。欢迎在评论区留言！
c++算法大全 文章被收录于专栏
本专栏收集了c++大部分基础算法，附有简介和代码。
投递美团等公司10个岗位
饿了么成长空间 204人发布
查看10道真题和解析