[关闭]
@Jerusalem 2015-11-15T12:51:39.000000Z 字数 1285 阅读 1170

POJ2774



  模板题。
  
  但很重要的是:max(trans(s,x))!=max(s)+1,这是因为在状态trans(s,x),可以抛弃掉状态s的某些Right集合中的点,从而扩大max(trans(s,x))。



  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <algorithm>
  7. using namespace std;
  8. const int maxnode=200005,sigma=26;
  9. int idx(char a)
  10. {
  11. return a-'a';
  12. }
  13. struct SAM{
  14. int root;
  15. int ch[maxnode][sigma];
  16. int pa[maxnode];
  17. int Max[maxnode];
  18. int last;
  19. int cnt;
  20. SAM(){
  21. root=last=cnt=1;
  22. memset(ch,0,sizeof(ch));
  23. memset(pa,0,sizeof(pa));
  24. }
  25. void Insert(char a){
  26. int p=last,np=++cnt;
  27. Max[np]=Max[p]+1;
  28. while(p&&!ch[p][idx(a)])
  29. ch[p][idx(a)]=np,p=pa[p];
  30. if(p==0)
  31. pa[np]=root;
  32. else{
  33. int q=ch[p][idx(a)];
  34. if(Max[q]==Max[p]+1)
  35. pa[np]=q;
  36. else{
  37. int nq=++cnt;
  38. memcpy(ch[nq],ch[q],sizeof(ch[nq]));
  39. Max[nq]=Max[p]+1;
  40. pa[nq]=pa[q];
  41. pa[q]=pa[np]=nq;
  42. while(ch[p][idx(a)]==q){
  43. ch[p][idx(a)]=nq;
  44. p=pa[p];
  45. }
  46. }
  47. }
  48. last=np;
  49. }
  50. };
  51. SAM Suffix;
  52. string P;
  53. void Solve(string S)
  54. {
  55. int leng=S.length();
  56. int u=1;
  57. int len=0,ans=0;
  58. for(int i=0;i<leng;i++){
  59. if(Suffix.ch[u][idx(S[i])])
  60. len++,u=Suffix.ch[u][idx(S[i])];
  61. else{
  62. while(u&&!Suffix.ch[u][idx(S[i])])
  63. u=Suffix.pa[u];
  64. if(u==0)
  65. u=1,len=0;
  66. else
  67. len=Suffix.Max[u]+1,u=Suffix.ch[u][idx(S[i])];
  68. }
  69. ans=max(ans,len);
  70. }
  71. cout<<ans<<endl;
  72. }
  73. void ReadData()
  74. {
  75. cin>>P;
  76. int len=P.length();
  77. for(int i=0;i<len;i++)
  78. Suffix.Insert(P[i]);
  79. cin>>P;
  80. }
  81. void Close()
  82. {
  83. fclose(stdin);
  84. fclose(stdout);
  85. }
  86. int main()
  87. {
  88. ReadData();
  89. Solve(P);
  90. Close();
  91. return 0;
  92. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注