今天我刷题了吗
搜索文档…
Manacher 算法
1
class Solution {
2
public:
3
string longestPalindrome(string s)
4
{
5
int len = (int)s.length();
6
int n = len * 2 + 2;
7
vector<int> mp(n, 0);
8
string ma("$#");
9
for (int i = 0; i < len; ++i) {
10
ma.push_back(s[i]);
11
ma.push_back('#');
12
}
13
int mx = 0, id = 0, p = 0;
14
for (int i = 0; i < n; ++i) {
15
mp[i] = mx > i ? min(mx - i, mp[id * 2 - i]) : 1;
16
if (i == 0) continue;
17
while (ma[i + mp[i]] == ma[i - mp[i]]) {
18
++mp[i];
19
}
20
if (mx < mp[i] + i) {
21
mx = mp[i] + i;
22
id = i;
23
}
24
if (mp[i] > mp[p]) {
25
p = i;
26
}
27
}
28
len = mp[p] - 1;
29
p = (p - len) / 2;
30
return s.substr(p, len);
31
}
32
};
Copied!
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
const int maxn = 11e6 + 10;
5
int mp[maxn << 1];
6
char s[maxn], ma[maxn << 1];
7
8
void manacher(int len)
9
{
10
memset(mp, 0, sizeof mp);
11
int l = 0;
12
ma[l++] = '#x27;;
13
ma[l++] = '#';
14
for (int i = 0; i < len; ++i) {
15
ma[l++] = s[i];
16
ma[l++] = '#';
17
}
18
ma[l] = '\0';
19
int mx = 0, id = 0;
20
for (int i = 0; i < l; ++i) {
21
mp[i] = mx > i ? min(mx - i, mp[id * 2 - i]) : 1;
22
while (ma[i + mp[i]] == ma[i - mp[i]]) ++mp[i];
23
if (mx < mp[i] + i) {
24
mx = mp[i] + i;
25
id = i;
26
}
27
}
28
}
29
30
int main()
31
{
32
#ifdef ONLINE_JUDGE
33
#else
34
freopen("input.txt", "r", stdin);
35
#endif
36
scanf("%s", s);
37
int len = (int)strlen(s);
38
manacher(len);
39
int res = 0;
40
for (int i = 0; i < len * 2 + 2; ++i) {
41
res = max(res, mp[i] - 1);
42
}
43
printf("%d\n", res);
44
return 0;
45
}
Copied!
最近更新 11mo ago
复制链接