最长回文子串
Manacher简介
Manacher算法，又叫“马拉车”算法，可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。
C++模板
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
37
38
39
40
41
42
43
44
45
46
47
48
| string Manacher(string s, int start, int end) {
int pos = 0;
int right = 0;
int ansPos = 0;
int ansLen = 0;
vector<int> len(end + 1, 0);
for (int i = start; i <= end; i++) {
if (i < right) {
len[i] = min(len[2 * pos - i], right - i);
}
else {
len[i] = 1;
}
while (s[i - len[i]] == s[i + len[i]]) {
len[i]++;
}
if (i + len[i] > right) {
right = i + len[i];
pos = i;
}
if (len[i] > ansLen) {
ansLen = len[i];
ansPos = i;
}
}
string t = s.substr(ansPos - ansLen + 1, 2 * ansLen - 1);
string ans = "";
for (char c : t) {
if (c != '#' && c != '&' && c != '^')
ans.push_back(c);
}
return ans;
}
string longestPalindrome(string s) {
string t = "&#";
for (char c : s) {
t.push_back(c);
t.push_back('#');
}
t.push_back('^');
return Manacher(t, 1, t.length() - 2);
}
|
