作者:mobiledu2502878383 | 来源:互联网 | 2023-06-08 16:01
Manacher算法(原理)
分i
=P的两种情况,P为右端边界+1,即不在回文字串中(废话)
一。i>=P,就以i为中心,重新找回文,下文while的代码,十分简单。
二。i
为什么要有min,因为右边是有边界的,同时右边在继续向右边开拓时也可能有新的更长回文。min只是定个Len[i]的起点。
(i取个大值与小值就更好理解这min了)
分别记为,i与j,i为右边的点,但有
#include
#include
#include
#include
#include
using namespace std;
char newn[2000];
int inti(char str[])
{
int i;
int len=strlen(str);
str[0]='$';
for(i=1;i<=2*len;i+=2) //这里为什么不用2*len+1 如len==5 1 3 5 7 9,对应0 1 2 3 4
{ //如果加1就有11,对应就有str[5],所以不行
newn[i]='#';
newn[i+1]=str[i/2];
}
newn[2*len+1]='#';
newn[2*len+2]='@';//不能和@相同 这个操作是防止越界
newn[2*len+3]=0;
return 2*len+1; newn[]构建新的数组。
}
int main()
{
char str[2000];
int Len[2000];
int len,i;
int maxn=0,ans=0,pos=0;
while(gets(str)) //这个输入使有问题的,因为是模板,所以没仔细
{
getchar();
len=inti(str);
memset(Len,0,sizeof(Len));
memset(newn,0,sizeof(newn));
for(i=1;i<=len;i++)
{
if(maxn>i)
Len[i]=min(maxn-i,Len[2*pos-i]); //Len[i]记录以i为中心,中心加一侧的长度。而Len[i]-1就是原回文字串的长度。
else //manacher算法的精髓之一。
Len[i]=1;
while(newn[i-Len[i]]==newn[i+Len[i]])
Len[i]++;
if(Len[i]+i>maxn)
{
maxn=Len[i]+i;
pos=i;
}
ans=max(ans,Len[i]);
}
printf("%d\n",ans-1);
}
}