正文
kuangbin专题十六 KMP&&扩展KMP HDU3068 最长回文
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
回文就是正反读都是一样的字符串,如aba, abba等
Input输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000Output每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000Output每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
aaaaabab
Sample Output
4
3马拉车裸题。
再次学习马拉车第一步：字符串预处理，保证长度都为奇数。
明确id，mx的含义 id为最远回文对应的中心位置，mx为最远回文位置
用p[i]记录以i为中心的最大回文半径第二步：求p[i]分两种情况：
一、mx > i
①，mx-i>p[i] 如图所示：红色部分为i的回文范围。i和j关于id对称。说明p[i]=p[j]=p[2*id-i]②，mx-i<=p[i]
如图所示，红色为中心为i的回文范围，如果i+p[i]>mx, 那么只能说明 mx-i 这一段是可以由之前的推出来的
因为 mx是以id为中心，对应最远的回文右边界。所以这种情况p[i]=mx-i
二、mx<=i说明根本不知道以后的情况，只能p[i] = 1
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char s[],snew[];
int p[]; int manacher(char* s) {
int l=;
snew[l++]='$';
snew[l++]='#';
for(int i=;s[i];i++) {
snew[l++]=s[i];
snew[l++]='#';
}
snew[l]='\0';
int id=,mx=,maxlen=-;
for(int i=;i<l;i++) {
p[i]=i<mx?min(p[*id-i],mx-i):;
while(snew[i+p[i]]==snew[i-p[i]]) p[i]++;
if(i+p[i]>mx) {
mx=i+p[i];
id=i;
}
if(p[i]>maxlen) maxlen=p[i]-;
}
return maxlen;
} int main() {
while(~scanf("%s",s)) {
printf("%d\n",manacher(s));
}
return ;
}
kuangbin专题十六 KMP&&扩展KMP HDU3068 最长回文的更多相关文章- Manacher（hdu3068最长回文）
浅谈manacher算法 manacher算法是我在网上无意中找到的,主要是用来求某个字符串的最长回文子串. 不过网上的版本还不太成熟,我就修改了下. 不要被manacher这个名字吓倒了,其实man ...
- hdu3068最长回文(Manacher算法)
简单来说这是个很水的东西.有点dp的思想吧.推荐两个博客,很详细. http://blog.csdn.net/xingyeyongheng/article/details/9310555 http:/ ...
- HDU3068 最长回文 MANACHER+回文串
原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=3068 Problem Description 给出一个只由小写英文字符a,b,c...y,z组成的字符 ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU2609 How many (最小字符串表示法)
Give you n ( n < 10000) necklaces ,the length of necklace will not large than 100,tell me How man ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU2328 Corporate Identity
Beside other services, ACM helps companies to clearly state their “corporate identity”, which includ ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU1238 Substrings
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU3336 Count the string
It is well known that AekdyCoin is good at string problems as well as number theory problems. When g ...
- kuangbin专题十六 KMP&;&;扩展KMP POJ3080 Blue Jeans
The Genographic Project is a research partnership between IBM and The National Geographic Society th ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU3746 Cyclic Nacklace
CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, ...
随机推荐- bind绑定参数
const curry = (fn) => (...args)=>fn.bind(null,...args); const split = curry((splitOn, str) =&g ...
- StartCom 申请 SSL 证书及 Nginx HTTPS 支持配置全攻略
来源:https://www.williamyao.com/index.php/archives/1397/ 前言 最近收到 StartCom 的邮件,数字证书即将过期,想到去年在 StartSSL ...
- 本地新建项目提交到github
1.在github上创建项目(可以添加README.md),创建后的地址为 https://github.com/xxx/xxx-demo.git 2.在eclipse上新建个quick-start的 ...
- JavaScript Patterns 6.1 Classical Versus Modern Inheritance Patterns
In Java you could do something like: Person adam = new Person(); In JavaScript you would do: var ada ...
- Java——包的概念及使用
package是在使用多个类或接口时,为了避免名称重复而采用的一种措施,直接在程序中加入package关键字即可 编译语法: javac -d . HelloWord.java -d:表示生成目录,生 ...
- ganymedssh2 java执行linux命令
需要下载ganymed-ssh2-262.jar package ganymed; import java.io.BufferedReader; import java.io.IOException; ...
- markdown语法学习效果预览
注: 结合markdown官方文档 其中大部分例子和说明文字都摘自官方文档 官方链接:Markdown: Basics (快速入门). 一 段落.标题.区块代码 Markdown 支持两种标题的语法, ...
- AngularJS自定义表单验证器
<!doctype html> <html ng-app="myApp"> <head> <script src="G:\\So ...
- Hadoop通过HCatalog编写Mapreduce任务访问hive库中schema数据
1.dirver package com.kangaroo.hadoop.drive; import java.util.Map; import java.util.Properties; impor ...
- Docker：Service
Prerequisites Install Docker version 1.13 or higher. Get Docker Compose. On Docker for Mac and Docke ...
浅谈manacher算法 manacher算法是我在网上无意中找到的,主要是用来求某个字符串的最长回文子串. 不过网上的版本还不太成熟,我就修改了下. 不要被manacher这个名字吓倒了,其实man ...
简单来说这是个很水的东西.有点dp的思想吧.推荐两个博客,很详细. http://blog.csdn.net/xingyeyongheng/article/details/9310555 http:/ ...
原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=3068 Problem Description 给出一个只由小写英文字符a,b,c...y,z组成的字符 ...
Give you n ( n < 10000) necklaces ,the length of necklace will not large than 100,tell me How man ...
Beside other services, ACM helps companies to clearly state their “corporate identity”, which includ ...
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X ...
It is well known that AekdyCoin is good at string problems as well as number theory problems. When g ...
The Genographic Project is a research partnership between IBM and The National Geographic Society th ...
CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, ...
- bind绑定参数
const curry = (fn) => (...args)=>fn.bind(null,...args); const split = curry((splitOn, str) =&g ...
- StartCom 申请 SSL 证书及 Nginx HTTPS 支持配置全攻略
来源:https://www.williamyao.com/index.php/archives/1397/ 前言 最近收到 StartCom 的邮件,数字证书即将过期,想到去年在 StartSSL ...
- 本地新建项目提交到github
1.在github上创建项目(可以添加README.md),创建后的地址为 https://github.com/xxx/xxx-demo.git 2.在eclipse上新建个quick-start的 ...
- JavaScript Patterns 6.1 Classical Versus Modern Inheritance Patterns
In Java you could do something like: Person adam = new Person(); In JavaScript you would do: var ada ...
- Java——包的概念及使用
package是在使用多个类或接口时,为了避免名称重复而采用的一种措施,直接在程序中加入package关键字即可 编译语法: javac -d . HelloWord.java -d:表示生成目录,生 ...
- ganymedssh2 java执行linux命令
需要下载ganymed-ssh2-262.jar package ganymed; import java.io.BufferedReader; import java.io.IOException; ...
- markdown语法学习效果预览
注: 结合markdown官方文档 其中大部分例子和说明文字都摘自官方文档 官方链接:Markdown: Basics (快速入门). 一 段落.标题.区块代码 Markdown 支持两种标题的语法, ...
- AngularJS自定义表单验证器
<!doctype html> <html ng-app="myApp"> <head> <script src="G:\\So ...
- Hadoop通过HCatalog编写Mapreduce任务访问hive库中schema数据
1.dirver package com.kangaroo.hadoop.drive; import java.util.Map; import java.util.Properties; impor ...
- Docker：Service
Prerequisites Install Docker version 1.13 or higher. Get Docker Compose. On Docker for Mac and Docke ...
