U - Palindrome Manacher
A string is said to be a palindrome if it reads the same both forwards and backwards, for example "madam" is a palindrome while "acm" is not.
The students recognized that this is a classical problem but couldn't come up with a solution better than iterating over all substrings and checking whether they are palindrome or not, obviously this algorithm is not efficient at all, after a while Andy raised his hand and said "Okay, I've a better algorithm" and before he starts to explain his idea he stopped for a moment and then said "Well, I've an even better algorithm!".
If you think you know Andy's final solution then prove it! Given a string of at most 1000000 characters find and print the length of the largest palindrome inside this string.
Input
Output
Sample Input
abcbabcbabcba
abacacbaaaab
END
Sample Output
Case 1: 13
Case 2: 6
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<cstring>
#include<fstream>
using namespace std;
#define MAXN 1000003
typedef long long LL;
/*
最长回文串的长度
*/
char a[MAXN];
char s[MAXN*];
int r[MAXN*];
void Manacher(int len)
{
int p=;
s[p++] = '$';
s[p++] = '#';
for(int i=;i<len;i++)
{
s[p++] = a[i];
s[p++] = '#';
}
s[p] = ; int Mx = ,pos = ;
for(int i=;i<p;i++)
{
r[i] = (i<Mx)? min(Mx-i,r[*pos-i]):;
while(s[i+r[i]]==s[i-r[i]])
r[i]++;
if(i+r[i]>Mx)
{
Mx = i+r[i];
pos = i;
}
}
}
int main()
{
int cas = ;
while(scanf("%s",a),a[]!='E')
{
int l = strlen(a);
Manacher(l);
int ans = ;
for(int i=;i<*l+;i++)
{
ans = max(ans,r[i]-);
}
printf("Case %d: %d\n",cas++,ans);
}
}
最新文章
- MFC操作excel
- openlayers 3 简书
- 基于RulesEngine的业务规则实现
- Arrays.asList()使用注意点
- Android SDK 更新镜像服务器
- MySql数据类型(转)
- Struts2 Convention插件的使用(1)
- Qt将表格table保存为excel(odbc方式)
- android网址
- java代码收藏:获取HttpServletRequest中某一前缀的参数
- bzoj 2073 暴力
- 微信小程序-列表渲染多层嵌套循环
- linux安装配置zookeeper-3.4.10
- JSON数据写入和解析
- js 实现List
- JustOj 1929: 多输入输出练习1
- Spring4.0之四:Meta Annotation(元注解)
- 跟我一起学Python-day1(条件语句以及初识变量)
- redis实现秒杀demo
- python学习笔记——提取网页中的信息正则表达式re