P3805 manacher 算法
时间限制(普通/Java):500MS/3000MS 内存限制:512.00MB
返回题目
描述
给出一个只由小写英文字符 a,b,c,…y,z 组成的字符串 S ,求 S 中最长回文串的长度 。
字符串长度为 n。
输入
一行小写英文字符 a,b,c,⋯,y,z 组成的字符串 S。
输出
一个整数表示答案。
样例输入
aaa
样例输出
3
思路
manacher 算法模板题
洛谷的刚开始看看了好久没看懂，看这个知乎的算法详解一遍就看懂了
https://www.zhihu.com/question/37289584
AC代码
#include <bits/stdc++.h>
using namespace std;
int ans[22000010];
string change(string s)
{
string temp;
temp+='~';
int len=s.length();
for(int i=0;i<len;i++)
temp+="#",temp+=s[i];
temp+="#_";
return temp;
}
int solve(string s)
{
int c=1,r=1;
int len=s.length();
for(int i=1;i<len;i++)
{
int tempi=2*c-i;
ans[i]=min(ans[tempi],r-i);
while (s[i+ans[i]+1]==s[i-ans[i]-1])
ans[i]++;
if(i+ans[i]>r)
{
c=i;
r=i+ans[i];
}
}
int res=0;
for(int i=1;i<len;i++)
{
if(ans[i]>res)res=ans[i];
}
return res;
}
signed main()
{
string s;
cin>>s;
int an;
an=solve(change(s));
cout<<an<<endl;
}