【模板】manacher 算法
题目描述
给出一个只由小写英文字符 \(\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z\) 组成的字符串 \(S\) ,求 \(S\) 中最长回文串的长度 。
字符串长度为 \(n\)。
输入格式
一行小写英文字符 \(\texttt a,\texttt b,\texttt c,\cdots,\texttt y,\texttt z\) 组成的字符串 \(S\)。
输出格式
一个整数表示答案。
样例 #1
样例输入 #1
aaa
样例输出 #1
3
提示
\(1\le n\le 1.1\times 10^7\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1.1e7+10;
char s[N],t[N<<1];
int p[N<<1];
void manacher()
{
int n=strlen(s+1);
int m=0;
t[++m]='$';
for(int i=1;i<=n;++i)
t[++m]=s[i],t[++m]='$';
int M=0,R=0;
for(int i=1;i<=m;++i)
{
p[i]=1;
if(i<=R)
{
p[i]=min(p[M*2-i],R-i+1);
}
int &k=p[i];
while(i-k>0&&i+k<=m&&t[i-k]==t[i+k]) k++;
if(i+k-1>R) M=i,R=i+k-1;
}
int ans=0;
for(int i=1;i<=m;++i) ans=max(p[i],ans);
cout<<ans-1<<'\n';
}
void solve()
{
cin>>s+1;
manacher();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
return 0;
}