[关闭]
@Junlier 2018-08-19T14:25:52.000000Z 字数 1376 阅读 2293

Manacher总结

字符串算法——Manacher

我的代码

学习：yyb
luogu题目模板
xzy的模板 

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define N 51000100
  17. using namespace std;
  18. const int Inf=1e9;
  20. int n,ans=1;
  21. int p[N];
  22. char S[N],s[N<<1];
  24. il int read()
  25. {
  26.     rg int s=0,m=0;rg char ch=getchar();
  27.     while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  28.     while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  29.     return m?-s:s;
  30. }
  32. il void change()
  33. {
  34.     s[0]=s[1]='#';
  35.     for(rg int i=0;i<n;++i)
  36.     {
  37.         s[(i<<1)+2]=S[i];
  38.         s[(i<<1)+3]='#';
  39.     }
  40.     s[n=(n<<1)+2]=0;
  41. }
  43. il void manacher()
  44. {
  45.     rg int mx=0,id;
  46.     for(rg int i=1;i<n;++i)
  47.     {
  48.         if(i<mx)p[i]=min(p[(id<<1)-i],mx-i);
  49.         else p[i]=1;
  50.         while(s[i+p[i]]==s[i-p[i]])p[i]++;
  51.         if(p[i]+i>mx)
  52.             mx=p[i]+i,id=i;
  53.     }
  54. }
  56. int main()
  57. {
  58.     cin>>S;
  59.     n=strlen(S);
  60.     change();
  61.     manacher();
  62.     for(rg int i=0;i<n;++i)
  63.         ans=max(ans,p[i]);
  64.     printf("%d\n",ans-1);
  65.     return 0;
  66. }

题单(xzy，都是xzy的没错)

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