1089 最长回文子串 V2（Manacher算法） 

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题

 收藏

 关注

输入Str（Str的长度 <= 100000)

输出最长回文子串的长度L。

daabaac

5

Manacher算法详解

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

char ch[maxn];

int vis[maxn];//记录第i个字符能够向左/右扩张的最大长度

int l;

void Manacher()

{

	int id,mx,ans;//id最大回文子串中心的位置，mx最大回文子串的边界

	id=mx=ans=0;

	for(int i=1;i<=2*l+1;i++)

	{

		if(mx>i) vis[i]=min(vis[2*id-i],mx-i);

        else vis[i]=1;

        while(ch[i+vis[i]]==ch[i-vis[i]]) vis[i]++;

        if(mx<vis[i]+i)

		{

            id=i;

            mx=vis[i]+i;

        }

        ans=max(ans,vis[i]);

	}

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

}

int main(int argc, char const *argv[])

{

	cin>>ch;

	l=strlen(ch);

	//处理字符串，在字符串开头，结尾都加上'#'

	for(int i=l;i>0;i--)//注意是从最后一位开始处理

	{

		ch[2*i]=ch[i-1];

		ch[2*i+1]='#';

	}

	ch[0]='$';//避免出现越界问题

	ch[1]='#';

	Manacher();

	return 0;

}