牛客小白月赛13 小A的回文串(Manacher)

链接:https://ac.nowcoder.com/acm/contest/549/B
来源:牛客网

题目描述

小A非常喜欢回文串,当然我们都知道回文串这种情况是非常特殊的。所以小A只想知道给定的一个字符串的最大回文子串是多少,但是小A对这个结果并不是非常满意。现在小A可以对这个字符串做一些改动,他可以把这个字符串最前面的某一段连续的字符(不改变顺序)移动到原先字符串的末尾。那么请问小A通过这样的操作之后(也可以选择不移动)能够得到最大回文子串的长度是多少。

输入描述:

一行一个字符串表示给定的字符串S一行一个字符串表示给定的字符串S

输出描述:

一行输出一个整数,表示通过这样的操作后可以得到最大回文子串的长度。
示例1

输入

复制

dcbaabc

输出

复制

7

说明

将前面的dcba移动到末尾变成abcdcba,这个字符串的最大回文子串就是它本身,长度为7

备注:

N表示字符串的长度,1≤N≤5000

解题思路:Manacher板子题,每次修改字符串后跑一遍Manacher即可,时间复杂度为O(N^2)
既然说到了Manacher,那就简答讲一下吧,至于详细的讲解过程,可以参考这篇博客:Manacher
回文字符串可能出现两种情况,一种是长度为奇数的,另一种为长度为偶数的,为了方便,我们可以对字符串进行处理,把它变成一个长度为奇数的字符串。比如字符串:acbbca,可以变成#a#c#b#b#c#a#(注意也可以加入其它字符,但加入的字符不能原字符串出现过的)
,为了防止匹配的时候出现越界的情况,还可以在字符串的最前面加入一个$字符(字符串中为出现过),这里,还需要定义一个数组P[],记录某回文字串的半径,就如$#a#c#b#b#c#a#,第8个字符#的p值为:7,它的坐标为7,此时回文串的长度为7-1=6,回文串的
起始位置为(7-7)/2=0,即坐标减去p的值然后除以二(相当于原字符串acbbca),此时我们可以得到此时的回文字串为acbbca。(想看推导过程可以参考上面推荐的那篇博客QAQ。。)、
这里插上此题的AC代码吧
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define ri register int
typedef long long ll; inline ll gcd(ll i,ll j){
return j==0?i:gcd(j,i%j);
}
inline ll lcm(ll i,ll j){
return i/gcd(i,j)*j;
}
inline void output(int x){
if(x==0){putchar(48);return;}
int len=0,dg[20];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
inline void read(int &x){
char ch=x=0;
int f=1;
while(!isdigit(ch)){
ch=getchar();
if(ch=='-'){
f=-1;
}
}
while(isdigit(ch))
x=x*10+ch-'0',ch=getchar();
x=x*f;
}
const int maxn=1e5+5;
void change(char * c,char * d){
int len=strlen(c);
d[0]='(';
int j=1;
for(int i=0;i<len;i++){
d[j++]='#';
d[j++]=c[i]; }
d[j]='#';
d[j+1]='\0';
// puts(d);
}
int manacher(char * c,char * d,int * p){
change(c,d);
int ans=-1;
int len=strlen(d);
int mx=0,id=0;//mx为回文串最右端,id为中心
for (int i = 1; i < len; i++)
{
if (i < mx)
p[i] = min(p[2 * id - i], mx - i);//这里是Manacher算法的核心
else
p[i] = 1;
while (d[i - p[i]] == d[i + p[i]])
p[i]++;
if (mx < i + p[i])
{
id = i;
mx = i + p[i];
}
ans=max(ans,p[i]-1);
}
return ans;
}
char ch[maxn*2+5];
char ch1[maxn];
int p[maxn*2+5];
int main(){
scanf("%s",ch1);
int ans=0;
int len=strlen(ch1);
for(int i=0;i<len;i++){
ans=max(manacher(ch1+i,ch,p),ans);
// cout<<ans<<endl;
ch1[i+len]=ch1[i];
}
cout<<ans;
return 0;
}

  

上一篇:10 steps to get Ruby on Rails running on Windows with IIS FastCGI- 摘自网络


下一篇:ruby on rails on windows