P3805 【模版】manacher算法

2018-06-17 22:16:18来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

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

字符串长度为n

输入输出格式

输入格式:

 

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

 

输出格式:

 

一个整数表示答案

 

输入输出样例

输入样例#1:
aaa
输出样例#1:
3

说明

字符串长度len <= 11000000

 

老吕教的manacher太low,,

写一个T一个,

以后改写位运算型的了。

一个点才300ms

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 #include<cstdlib>
 8 #define lli long long int 
 9 using namespace std;
10 const lli MAXN=31000011;
11 char s[MAXN];
12 char str[MAXN];
13 int ans[MAXN];
14 int len=0;
15 int ls=0;
16 void getstr()
17 {
18     str[0]='#';
19     str[1]='#';
20     for(int i=0;i<ls;i++)
21     str[(i<<1)+2]=s[i],str[(i<<1)+3]='#';
22     ls=(ls<<1)+2;
23     str[ls]=0;
24 }
25 void manacher()
26 {
27     getstr();
28     int mx=0,id=0;
29     
30     len=strlen(str);
31     for(int i=1;i<len;i++)
32     {
33         if(mx>i)
34             ans[i]=min(ans[2*id-i],mx-i);
35         else ans[i]=1;
36         while(str[i+ans[i]]==str[i-ans[i]])
37             ++ans[i];
38         if(i+ans[i]>mx)
39             mx=i+ans[i],id=i;
40             
41     }
42 }
43 int main()
44 {
45     scanf("%s",s);
46     ls=strlen(s);
47     manacher();
48     int out=0;
49     for(int i=0;i<len;i++)
50         out=max(out,ans[i]);
51     printf("%d",out-1);
52     return 0;
53 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1982 小朋友的数字

下一篇:P1112 波浪数