SPOJ/NSUBSTR.cc

   1 #include <cstdio>
   2 #include <cstring>
   3 #include <algorithm>
   4
   5 #define rep(i,p,q) for (i=p; i<=q; ++i)
   6
   7 using namespace std;
   8
   9 const int maxn=250000+10;
  10
  11 char str[maxn];
  12
  13 struct SAM
  14 {
  15         int len;
  16         SAM *fail,*next[26];
  17 } sam[maxn*2],*root,*last;
  18
  19 int ans[maxn]={0},cnt=0,i,sum[maxn*2],queue[maxn*2],w[maxn*2];
  20
  21 void insert(int ch)
  22 {
  23         SAM *p=last,*np=&sam[++cnt];
  24         np->len=last->len+1;
  25         last=np;
  26         for (; p && !p->next[ch]; p=p->fail) p->next[ch]=np;
  27         if (!p) np->fail=root; else
  28                 if (p->next[ch]->len==p->len+1) np->fail=p->next[ch]; else
  29                 {
  30                         SAM *q=p->next[ch],*nq=&sam[++cnt];
  31                         *nq=*q;
  32                         nq->len=p->len+1;
  33                         q->fail=np->fail=nq;
  34                         for (; p && p->next[ch]==q; p=p->fail) p->next[ch]=nq;
  35                 }
  36 }
  37
  38 int main()
  39 {
  40         scanf("%s",str+1);
  41         memset(sam,0,sizeof(sam));
  42         last=root=&sam[++cnt];
  43         int n=strlen(str+1);
  44         rep(i,1,n) insert(str[i]-'a');
  45         memset(sum,sizeof(sum),0);
  46         SAM *now=root;
  47         rep(i,1,cnt) ++sum[sam[i].len];
  48         rep(i,1,n) sum[i]+=sum[i-1];
  49         rep(i,1,cnt) queue[sum[sam[i].len]--]=i;
  50         rep(i,1,n) ++w[(now=now->next[str[i]-'a'])-sam];
  51         for (i=cnt; i; --i)
  52         {
  53                 ans[sam[queue[i]].len]=max(ans[sam[queue[i]].len],w[queue[i]]);
  54                 if (sam[queue[i]].fail) w[sam[queue[i]].fail-sam]+=w[queue[i]];
  55         }
  56         for (i=n; i>1; --i) ans[i-1]=max(ans[i-1],ans[i]);
  57         rep(i,1,n) printf("%d\n",ans[i]);
  58         return 0;
  59 }