luogu P3805 【模板】manacher算法

题目描述

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.

字符串长度为n

输入格式

一行小写英文字符a,b,c...y,z组成的字符串S

输出格式

一个整数表示答案

马拉车算法，O(n)解决，巧妙的利用对称性

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=11000000+20;

char data[N<<1];

int p[N<<1],cnt,ans;

inline void qr(){

	char c=getchar();

	data[0]='~',data[cnt=1]='|';

	while(c<'a'||c>'z')c=getchar();

	while(c>='a'&&c<='z')

	data[++cnt]=c,data[++cnt]='|',c=getchar();

}

int main(){

	qr();

	for(int t=1,r=0,mid=0;t<=cnt;++t){

		if(t<=r)p[t]=min(p[(mid<<1)-t],r-t+1);

		while(data[t-p[t]]==data[t+p[t]])++p[t];

		if(p[t]+t>r)r=p[t]+t-1,mid=t;

		if(p[t]>ans)ans=p[t];

	}

	printf("%d\n",ans-1);

}

巴特西

luogu P3805 【模板】manacher算法

题目描述

输入格式

输出格式

最新文章

热门文章