Manacher

2020-03-07

字数统计: 243字 | 阅读时长≈ 1分钟

Manacher的总结

题目传送门：POJ-3974 Palindrome

求最长回文字串

Manacher模板题

1	#include <cstring>
2	#include <cstdio>
3	#include <algorithm>
4	using namespace std;
5	char a[1000005];
6	char ma[2000005];
7	int mp[2000005];
8	int main()
9	{
10	int ca = 1;
11	while(scanf("%s", a) != EOF && strcmp(a, "END") != 0)
12	{
13	int n = strlen(a), i, l = 0;
14	ma[l++] = '$';
15	ma[l++] = '#';
16	for(i = 0; i < n; i++)
17	{
18	ma[l++] = a[i];
19	ma[l++] = '#';
20	}
21	ma[l] = 0;
22	int mx = 0, id = 0;
23	int ans = 0;
24	for(i = 0; i < l; i++)
25	{
26	mp[i] = mx > i ? min(mp[2 * id - i], mx - i):1;
27	while(ma[i + mp[i]] == ma[i - mp[i]])mp[i]++;
28	if(i + mp[i] > mx)
29	{
30	mx = i + mp[i];
31	id = i;
32	}
33	ans = max(ans, mp[i] - 1);
34	}
35	printf("Case %d: %d\n", ca++, ans);
36
37	}
38	return 0;
39	}