【模板】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

提示

\(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;
}