P3805 【模版】manacher算法（manacher）

题目描述

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.

字符串长度为n

输入输出格式

输入格式：

一行小写英文字符a,b,c...y,z组成的字符串S

输出格式：

一个整数表示答案

输入输出样例

输入样例#1：

aaa

输出样例#1：

说明

字符串长度len <= 11000000

分析

str数组是原来的数组，s是后来的数组。

那样例说，str：aaa，s：##a#a#a#，转变的过程中的左移等位运算模拟一下就会很清楚。

原先是一个一个赋值，s[k++] = '#', str[k++] = s[i];结果tle最后一个点，改成位运算好了。

manacher模板

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define MAXN 31000000
 5 using namespace std;
 6 
 7 char s[MAXN],str[MAXN];
 8 int p[MAXN],len;
 9 
10 void init()
11 {
12     len = strlen(str);
13     s[0] = '#';
14     for (int i=0; i<len; ++i)
15     {
16         s[i<<1|1] = '#';
17         s[(i+1)<<1] = str[i];
18     }
19     s[len<<1|1] = '#';
20     len = (len<<1|1);
21 }
22 int manacher()
23 {
24     int mx = 0, id;
25     for (int i=1; i<=len; ++i)
26     {
27         if (mx>i) p[i] = min(p[id<<1-1],mx-i);
28         else p[i] = 1;
29         while (s[i+p[i]]==s[i-p[i]]) p[i]++;
30         if (p[i]+i>mx) 
31             mx = p[i]+i, id = i;
32     }
33     int ans = 0;
34     for (int i=1; i<len; ++i) ans = max(ans,p[i]);
35     return ans-1;
36 }
37 int main()
38 {
39     scanf("%s",str);
40     init();
41     printf("%d",manacher());
42     return 0;
43 }