后缀自动机

From axuhongbo, 3 Years ago, written in C++, viewed 404 times.
URL http://axuhongbo.top/paste/view/4d71db84 Embed
Download Paste or View Raw
  1. code:
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #define ll long long
  7. using namespace std;
  8. const int N=2010000;
  9. char s[N];
  10. int fa[N],ch[N][26],len[N],siz[N];
  11. int lst=1,node=1,l,t[N],A[N];
  12. ll ans;
  13. void Extend(int c)
  14. {
  15.     /*
  16.       2+2+2+3行,那么多while但是复杂度是O(n)
  17.      */
  18.     int f=lst,p=++node;lst=p;
  19.     len[p]=len[f]+1;siz[p]=1;
  20.     /*
  21.       f为以c结尾的前缀的倒数第二个节点,p为倒数第一个(新建)
  22.       len[i] 表示i节点的longest,不用记录shortest(概念在hihocoder后缀自动机1上讲得十分详细)
  23.       siz[i]表示以i所代表的endpos的集合元素大小,即所对应的字符串集出现的次数
  24.       不用担心复制后的siz,在parent树上复制后的点的siz是它所有儿子siz之和,比1多
  25.      */
  26.     while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
  27.     if(!f) {fa[p]=1;return;}
  28.     /*
  29.       把前面的一段没有c儿子的节点的c儿子指向p
  30.       Situation 1 如果跳到最前面的根的时候,那么把p的parent树上的父亲置为1
  31.      */
  32.     int x=ch[f][c],y=++node;
  33.     if(len[f]+1==len[x]) {fa[p]=x;node--;return;}
  34.     /*
  35.       x表示从p一直跳parent树得到的第一个有c儿子的节点的c儿子
  36.       Situation 2 如果节点x表示的endpos所对应的字符串集合只有一个字符串,那么把p的parent树父亲设置为x
  37.       Situation 2 和 Situation 3 本质不同!!!与机房dalao们讨论两天才知道Situation 2 必须特判的原因!!!详见上方链接的博客
  38.      */
  39.     len[y]=len[f]+1; fa[y]=fa[x]; fa[x]=fa[p]=y;
  40.     memcpy(ch[y],ch[x],sizeof(ch[y]));
  41.     while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
  42.     /*
  43.       Situation 3 否则把x点复制一遍(parent树父亲、儿子),同时len要更新
  44.                  (注意len[x]!=len[f]+1,因为通过加点会使x父亲改变)
  45.                   然后把x点和p点的父亲指向复制点y,再将前面所有本连x的点连向y
  46.      */
  47. }
  48. int main()
  49. {
  50.     //Part 1 建立后缀自动机
  51.     scanf("%s",s); l=strlen(s);
  52.     for(int i=l;i>=1;i--) s[i]=s[i-1];s[0]=0;
  53.     for(int i=1;i<=l;i++) Extend(s[i]-'a');
  54.     //Part 2 按len从大到小排序(和SA好像啊)后计算答案
  55.     for(int i=1;i<=node;i++) t[len[i]]++;
  56.     for(int i=1;i<=node;i++) t[i]+=t[i-1];
  57.     for(int i=1;i<=node;i++) A[t[len[i]]--]=i;
  58.     for(int i=node;i>=1;i--)
  59.     {//从小到大枚举,实际上在模拟parent树的DFS
  60.         int now=A[i];siz[fa[now]]+=siz[now];
  61.         if(siz[now]>1) ans=max(ans,1ll*siz[now]*len[now]);
  62.     }
  63.     printf("%lld\n",ans);
  64.     return 0;
  65. }
  66.  

Replies to 后缀自动机 rss

Title Name Language When
Re: 后缀自动机 Harmless Rhinoceros cpp 3 Years ago.

Reply to "后缀自动机"

Here you can reply to the paste above

captcha