模板 manacher算法

技术交流学习或者有任何问题欢迎加群

编程技术交流群 : 154514123 爱上编程      Java技术交流群 : 6128790  Java

标签:chang   表示   include   ref   article   最长回文串   strong   ron   manacher   

题目描述

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

字符串长度为n

输入输出格式

输入格式:

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

输出格式:

一个整数表示答案

输入输出样例

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

说明

字符串长度len <= 11000000

http://blog.csdn.net/dyx404514/article/details/42061017

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 char ch[11000005],s[30000005];
 8 int len[30000005],n,ans,tot;
 9 void change()
10 {int i,j;
11   for (i=0;i<n;i++)
12     {
13       s[++tot]=#;
14       s[++tot]=ch[i];
15     }
16   s[++tot]=#;
17   s[++tot]=$;
18   n=tot;
19 }
20 void manacher()
21 {int i;
22   int mx=0,po=0;
23   for (i=1;i<=n;i++)
24     {
25       if (mx>i)
26     len[i]=min(mx-i,len[2*po-i]);
27       else len[i]=1;
28       while (s[i-len[i]]==s[i+len[i]]) len[i]++;
29       if (len[i]+i>mx)
30     {
31       po=i;
32       mx=len[i]+i;
33     }
34       ans=max(ans,len[i]-1);
35     }
36 }
37 int main()
38 {
39   scanf("%s",ch);
40   n=strlen(ch);
41   change();
42   manacher();
43   cout<<ans;
44 }

 

模板 manacher算法

标签:chang   表示   include   ref   article   最长回文串   strong   ron   manacher   

原文:https://www.cnblogs.com/Y-E-T-I/p/8383603.html

技术交流学习或者有任何问题欢迎加群

编程技术交流群 : 154514123 爱上编程      Java技术交流群 : 6128790  Java

广告推荐

讨论区