[关闭]
@xzyxzy 2018-07-02T18:18:52.000000Z 字数 933 阅读 1493

Manacher

字符串

作业部落

评论地址

极易理解，挂一个dalao的博客
贴个代码吧。

  1. //luogu P3805【模板】manacher算法
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. using namespace std;
  7. int l,C,R,p[31000000],Ans;
  8. char s[31000000];
  9. int main()
  10. {
  11.     s[++l]='#';char ch=getchar();
  12.     while(ch>'z'||ch<'a') ch=getchar();
  13.     while(ch>='a'&&ch<='z')
  14.     {
  15.         s[++l]=ch;s[++l]='#';
  16.         ch=getchar();
  17.     }
  18.     for(int i=1;i<=l;i++)
  19.     {
  20.         p[i]=i<R?min(p[C*2-i],R-i):1;
  21.         while(s[i+p[i]]==s[i-p[i]]&&i-p[i]>=1&&i+p[i]<=l) p[i]++;
  22.         if(i+p[i]>R) {R=i+p[i];C=i;}
  23.         Ans=max(Ans,p[i]-1);
  24.     }
  25.     printf("%d\n",Ans); return 0;
  26. }

挂个题单

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注