L2-008 最长对称子串（manacher()算法）

一、manacher()算法

1.可以在o(n)的时间内求出一个字符串的最长回文串

假设n<=1.1*10^7

N=3e7=n*2

2.原理

 manacher算法
可以在o(n)的时间内求出一个字符串的最长回文串
1.改造字符串，在字符之间和串两端插入#,
都变成奇回文串
s[0]='$'是哨兵（边界）
string str,s;
cin>>s;
len=s.size();
str+='$';
for(i=0;i<len;i++)
{
	str+='#';
	str+=s[i];
}
str+='#';
len=str.size();
cout<<manacher()<<endl;
2.回文半径d[i]:以i为中心的最长回文串的长度的一半 
# a # a # [b] # a #
1 2 3 2 1  4  1 2 1
3 1 右端点处在边缘位置 
7/2+1=4
3.加速盒子[l,r];
维护右端点最靠右的最长回文串，
利用盒子，借助之前的状态来加速计算
新的状态。盒内d[i]可以利用对称点d值
转移，盒外暴力

计算完前i-1个d函数，维护盒子[l,r];
1.如果i<=r(在盒内) i的对称点 r-i+l;
if(d[r-i+l]<r-i+1)//r-i偏移量  l+偏移量=对称点 
    d[i]=d[i-l+1];
else（i<=r） 
    d[i]=r-i+1;
2.如果i>r在盒外，从i开始枚举
3.求出d[i]
if(i+d[i]-1>r)
    l=i-d[i]+1;
    r=i+d[i]-1;
    
void get_d(char *s,int n)
{
	d[1]=1;
	for(i=2,l,r=1;i<=n;i++)
	{
		if(i<=r)
		   d[i]=min(d[r-i+1],r-i+1);
		while(s[i-d[i]]==s[i+d[i]])
		   d[i]++;
		if(i+d[i]-1>r)
		{
			l=i-d[i]+1;
			r=i+d[i]-1;
		}
	 } 
}

 
 

二、例题

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：

输入在一行中给出长度不超过1000的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

输入样例：

Is PAT&TAP symmetric?

输出样例：

11

三、代码

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cmath>
using namespace std;
const int N=2e7;
string str,s;
int p[N];
int n,len;
int manacher()
{
	p[0]=0;
	int L=0,R=0,sum=0,i;
	for(i=1;i<len;i++)
	{
		if(i>R)
		    p[i]=1;
		else
		    p[i]=min(p[2*L-i],R-i);
		while(str[i-p[i]]==str[i+p[i]])
		    p[i]++;
		if(i+p[i]>R)
		{
			L=i;
			R=i+p[i];
			sum=max(sum,p[i]);
		}
	}
	return sum-1;
}
int main()
{
	getline(cin,s);
	len=s.size();
	int k=0;
	//str[k++]='&';
	str+='&';
	for(int i=0;i<len;i++)
	{
//		str[k++]='#';
//		str[k++]=s[i];
        str+='#';
        str+=s[i];
	}
	str+='#'; 
	//str[k++]='#';
	len=str.size();
	cout<<manacher()<<endl;
	return 0;
}