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

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;
  19. int n,ans=1;
  20. int p[N];
  21. char S[N],s[N<<1];
  22. il int read()
  23. {
  24. rg int s=0,m=0;rg char ch=getchar();
  25. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  26. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  27. return m?-s:s;
  28. }
  29. il void change()
  30. {
  31. s[0]=s[1]='#';
  32. for(rg int i=0;i<n;++i)
  33. {
  34. s[(i<<1)+2]=S[i];
  35. s[(i<<1)+3]='#';
  36. }
  37. s[n=(n<<1)+2]=0;
  38. }
  39. il void manacher()
  40. {
  41. rg int mx=0,id;
  42. for(rg int i=1;i<n;++i)
  43. {
  44. if(i<mx)p[i]=min(p[(id<<1)-i],mx-i);
  45. else p[i]=1;
  46. while(s[i+p[i]]==s[i-p[i]])p[i]++;
  47. if(p[i]+i>mx)
  48. mx=p[i]+i,id=i;
  49. }
  50. }
  51. int main()
  52. {
  53. cin>>S;
  54. n=strlen(S);
  55. change();
  56. manacher();
  57. for(rg int i=0;i<n;++i)
  58. ans=max(ans,p[i]);
  59. printf("%d\n",ans-1);
  60. return 0;
  61. }

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

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