P3805 【模版】manacher算法

题目描述

给出一个只由小写英文字符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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小工匠技术圈

【小工匠聊密码学】-- Base64算法

15930
来自专栏李蔚蓬的专栏

Java基础知识的全面巩固_note1(附各种demo code)

上面的cmd中,javac程序是一个Java编译器,它将文件Welcome.java编译成Welcome.class.java程序启动Java虚拟机。虚拟机执行...

10620
来自专栏Hongten

java中的移位运算符:<<,>>,>>>总结

value >>> num     --   num 指定要移位值value 移动的位数。

26050
来自专栏calmound

Prim

1.dist[n]并不是记录该最小生成树的最小权值 2.两个for(j)循环的意义不一样,第一个是寻找与k点相邻的最小边,第二个是更新与k点相邻的边,当然dis...

38880
来自专栏ShaoYL

OC正则表达式的简单使用

384130
来自专栏数据结构与算法

1545 最简单排序

个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

28360
来自专栏一个会写诗的程序员的博客

第11章 运算符重载与约定第11章 运算符重载与约定

我们在《第2章 Kotlin 语法基础》中已经学习过关于运算符的相关内容,本章将继续深入探讨Kotlin中的运算符的重载与约定。

16640
来自专栏Linux驱动

6.QT-简易计算器实现(详解)

41650
来自专栏DT乱“码”

实现MD5加密

/**  * 实现MD5加密  *  */ public class MD5 {  /**   * 获取加密后的字符串   * @param ...

25090
来自专栏数据结构与算法

1102 A-B数对

题目描述 出题是一件痛苦的事情! 题目看多了也有审美疲劳,于是我舍弃了大家所熟悉的A+B Problem,改用A-B了哈哈! 好吧,题目是这样的:给出一串数以及...

404130

扫码关注云+社区

领取腾讯云代金券