[关闭]
@Jerusalem 2015-11-16T09:08:58.000000Z 字数 1798 阅读 1394

POJ1743



  SAM傻逼题。
  


  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. using namespace std;
  8. const int maxnode=40005,sigma=180,INF=0x3f3f3f3f;
  9. struct SAM{
  10. int root,cnt,last;
  11. int ch[maxnode][sigma];
  12. int Max[maxnode];
  13. int l[maxnode];
  14. int r[maxnode];
  15. int fa[maxnode];
  16. SAM(){
  17. root=cnt=last=1;
  18. memset(ch,0,sizeof(ch));
  19. memset(Max,0,sizeof(Max));
  20. memset(fa,0,sizeof(fa));
  21. memset(l,0,sizeof(l));
  22. memset(r,0,sizeof(r));
  23. }
  24. int newnode(){
  25. cnt++;
  26. memset(ch[cnt],0,sizeof(ch[cnt]));
  27. return cnt;
  28. }
  29. void Clear(){
  30. memset(l,0,sizeof(l));
  31. memset(r,0,sizeof(r));
  32. memset(fa,0,sizeof(fa));
  33. memset(Max,0,sizeof(Max));
  34. cnt=0;
  35. last=root=newnode();
  36. }
  37. void Insert(int a){
  38. int p=last;
  39. int np=newnode();Max[np]=Max[p]+1;l[np]=r[np]=Max[np];
  40. while(p&&!ch[p][a])
  41. ch[p][a]=np,p=fa[p];
  42. if(p==0)
  43. fa[np]=root;
  44. else{
  45. int q=ch[p][a];
  46. if(Max[q]==Max[p]+1)
  47. fa[np]=q;
  48. else{
  49. int nq=newnode();
  50. memcpy(ch[nq],ch[q],sizeof(ch[q]));
  51. l[nq]=INF;r[nq]=0;
  52. Max[nq]=Max[p]+1;
  53. fa[nq]=fa[q];
  54. fa[q]=fa[np]=nq;
  55. while(p&&ch[p][a]==q)
  56. ch[p][a]=nq,p=fa[p];
  57. }
  58. }
  59. last=np;
  60. }
  61. };
  62. SAM Suffix;
  63. int a[maxnode];
  64. int v[maxnode];
  65. int q[maxnode];
  66. int n;
  67. void Solve()
  68. {
  69. while(cin>>n&&n){
  70. Suffix.Clear();
  71. int ans=0;
  72. for(int i=1;i<=n;i++)
  73. scanf("%d",&a[i]);
  74. for(int i=1;i<n;i++)
  75. a[i]=a[i+1]-a[i]+88;
  76. for(int i=1;i<n;i++)
  77. Suffix.Insert(a[i]);
  78. memset(v,0,sizeof(v));
  79. for(int i=1;i<=Suffix.cnt;i++)
  80. v[Suffix.Max[i]]++;
  81. for(int i=1;i<n;i++)
  82. v[i]+=v[i-1];
  83. for(int i=1;i<=Suffix.cnt;i++)
  84. q[v[Suffix.Max[i]]--]=i;
  85. for(int i=Suffix.cnt;i>=1;i--){
  86. int p=q[i];
  87. Suffix.l[Suffix.fa[p]]=min(Suffix.l[Suffix.fa[p]],Suffix.l[p]);
  88. Suffix.r[Suffix.fa[p]]=max(Suffix.r[Suffix.fa[p]],Suffix.r[p]);
  89. }
  90. for(int i=Suffix.cnt;i>=1;i--)
  91. ans=max(ans,min(Suffix.Max[i],Suffix.r[i]-Suffix.l[i]));
  92. cout<<(ans<4?0:ans+1)<<endl;
  93. }
  94. }
  95. void ReadData()
  96. {
  97. freopen("POJ1743.in","r",stdin);
  98. }
  99. void Close()
  100. {
  101. fclose(stdin);
  102. fclose(stdout);
  103. }
  104. int main()
  105. {
  106. ReadData();
  107. Solve();
  108. Close();
  109. return 0;
  110. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注