Re: 后缀自动机

From Harmless Rhinoceros, 3 Years ago, written in C++, viewed 444 times. This paste is a reply to 后缀自动机 from axuhongbo - view diff
URL http://axuhongbo.top/paste/view/ee7ccd4d Embed
Download Paste or View Raw
  1. 853c
  2. #include<bits/stdc++.h>
  3. #define N 2000005
  4. typedef long long ll;
  5. using namespace std;
  6. char s[N];
  7. int a[N],c[N],size[N],n;
  8. ll ans=0;
  9. struct SuffixAutoMaton{
  10.     int last,cnt;int ch[N<<1][26],fa[N<<1],l[N<<1];
  11.     void ins(int c){
  12.         int p=last,np=++cnt;last=np;l[np]=l[p]+1;
  13.         for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
  14.         if(!p)fa[np]=1;
  15.         else{
  16.             int q=ch[p][c];
  17.             if(l[p]+1==l[q])fa[np]=q;
  18.             else{
  19.                 int nq=++cnt;l[nq]=l[p]+1;
  20.                 memcpy(ch[nq],ch[q],sizeof(ch[q]));
  21.                 fa[nq]=fa[q];fa[q]=fa[np]=nq;
  22.                 for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
  23.             }
  24.         }
  25.         size[np]=1;
  26.     }
  27.     void build(){
  28.         scanf("%s",s+1);int len=strlen(s+1);
  29.         last=cnt=1;for(int i=1;i<=len;i++)ins(s[i]-'a');
  30.     }
  31.     void calc(){
  32.         for(int i=1;i<=cnt;i++)c[l[i]]++;
  33.         for(int i=1;i<=cnt;i++)c[i]+=c[i-1];
  34.         for(int i=1;i<=cnt;i++)a[c[l[i]]--]=i;
  35.         for(int i=cnt;i;i--){
  36.             int p=a[i];
  37.             size[fa[p]]+=size[p];
  38.             if(size[p]>1)ans=max(ans,1LL*size[p]*l[p]);
  39.         }
  40.         printf("%lld\n",ans);
  41.     }
  42. }sam;
  43. int main(){
  44.     sam.build();
  45.     sam.calc();
  46. }

Reply to "Re: 后缀自动机"

Here you can reply to the paste above

captcha