luogu P3805 【模板】manacher算法
analysis
先考虑一般的判断回文算法:拓展一个新点时,从这个点左右两边第一个位置开始向两边拓展,然后继续下一个点
而manacher算法的核心就是:拓展一个新点时,我们不必从这个点左右两边第一个位置开始向两边拓展,可以预先确定一部分回文串。
至于如何预先确定等细节,附上几篇blog:
https://cloud.tencent.com/developer/news/312855
https://www.cnblogs.com/grandyang/p/4475985.html
https://segmentfault.com/a/1190000008484167?utm_source=tag-newest
code
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num); memset(arry,num,sizeof(arry));
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
int maxx=-INT_MAX;
const int maxn=11000000+10;
char s[maxn];/////
char data[maxn<<1];
int p[maxn<<1];
int LEN;
inline int read()
{
int _ans=0;bool _neg=false;char _r=getchar();
while(_r>'9'||_r<'0'){if(_r=='-')_neg=true;_r=getchar();}
while(_r>='0'&&_r<='9'){_ans=_ans*10+_r-'0';_r=getchar();}
return (_neg)?-_ans:_ans;
}
inline void init()
{
int _len=strlen(s);
int _p=0;
data[_p++]='&';
while(_p<_len*2)
{
data[_p++]='#';
data[_p]=s[(_p/2)-1];
++_p;
}
data[_p]='#';
}
inline void GETP()
{
clean(p,0);
int _len=strlen(data);
int maxrpos=0;
int maxmidpos=0;
loop(i,1,_len)
{
p[i]=(maxrpos>i)?(min(maxrpos-maxmidpos,p[maxmidpos-(i-maxmidpos)])):(1);
while(data[i+p[i]]==data[i-p[i]])++p[i];
maxx=max(maxx,p[i]);
if(p[i]>maxrpos-maxmidpos)
{
maxrpos=i+p[i];
maxmidpos=i;
}
}
printf("%d",maxx-1);
}
int main()
{
scanf("%s",s);
LEN=strlen(s);
init();
GETP();
return 0;
}