看了好几篇博客,最后有思路的是一篇用pyhton写的,传送门

马拉车算法分为几个步骤:
1.字符中插入特殊字符,通常插入”#”,插入后字符串必会变成一个奇数串,因为插入的字符个数是len+1。首尾加上不同的字符例如&¥,简化边界情况越界判断。

2.计算半径数组p

3.数组p中最大值,即为最长回文子子串的半径
根据半径数组 p 的定义,如果最大值对应位置为 i,则最大回文子串为 ss[i - p[i] : i + p[i] + 1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
string Manacher(string s){
//改造字符串
string res="$#";
for (int i=0;i<s.size();i++){
res += s[i];
res +="#";
}
//p数组的构建
vector <int> p(res.size(),0);

int mi= 0,right = 0;//mi为最大回文串对应中心点,right为该回文串能到达的最右端值
int maxlen = 0,maxpoint = 0;//标记的最大回文串长度和中心点位置

for (int i=1;i<res.size();i++){
p[i] = right > i ?min(p[2*mi-i],right-i):1;//关键句

while (res[i+p[i]] == res[i-p[i]]) ++p[i];
if (right < i+p[i]){
right = i+p[i];
mi = i;
}

if (maxlen < p[i]) {
maxlen = p[i];
maxpoint = i;
}
}
return s.substr((maxpoint-maxlen)/2,maxlen-1);
}
int main(){
string s;
cin >> s;
cout << Manacher(s).size();
}

板子题

洛谷 P3805 【模板】manacher算法