BZOJ1396:识别子串(SAM)

Description

Input

一行,一个由小写字母组成的字符串S,长度不超过10^5

Output

L行,每行一个整数,第i行的数据表示关于S的第i个元素的最短识别子串有多长.

Sample Input

agoodcookcooksgoodfood

Sample Output

1
2
3
3
2
2
3
3
2
2
3
3
2
1
2
3
3
2
1
2
3
4

Solution

1A挺开心的省得调了
对于SAM上的每一个节点，我们只需要考虑right集合大小为1的
设一个right集合大小为1的点结束点在endpos，有效长度为[l,r]
那么对于区间[endpos-r+1,endpos-l+1]，这个点的贡献为endpos-i+1，用一颗线段树维护endpos+1，i最后计算贡献
对于区间[endpos-l+1,endpos],这个点的贡献为l，再开一颗线段树维护l
最后扫一遍单点查询最小值就好了
标记永久化好像非常短还好写= =

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (200000+1000)

 using namespace std;

 char s[N];

 int Ans,n;

 struct SGT

 {

     int Segt[N<<];

     SGT(){memset(Segt,0x7f,sizeof(Segt));}

     void Update(int now,int l,int r,int l1,int r1,int k)

     {

         if (r<l1 || l>r1) return;

         if (l1<=l && r<=r1){Segt[now]=min(Segt[now],k);return;}

         int mid=(l+r)>>;

         Update(now<<,l,mid,l1,r1,k); Update(now<<|,mid+,r,l1,r1,k);

     }

     void Query(int now,int l,int r,int x)

     {

         Ans=min(Ans,Segt[now]);

         if (l==r) return;

         int mid=(l+r)>>;

         if (x<=mid) Query(now<<,l,mid,x);

         else Query(now<<|,mid+,r,x);

     }

 }SGT[];

 struct SAM

 {

     int fa[N],son[N][],right[N],step[N],End[N],od[N],wt[N];

     int p,q,np,nq,last,cnt;

     SAM(){last=++cnt;}

     void Insert(int x,int pos)

     {

         p=last; last=np=++cnt; step[np]=step[p]+; right[np]=; End[np]=pos;

         while (p && !son[p][x]) son[p][x]=np,p=fa[p];

         if (!p) fa[np]=;

         else

         {

             q=son[p][x];

             if (step[p]+==step[q]) fa[np]=q;

             else

             {

                 nq=++cnt; step[nq]=step[p]+;

                 memcpy(son[nq],son[q],sizeof(son[q]));

                 fa[nq]=fa[q]; fa[q]=fa[np]=nq;

                 while (son[p][x]==q) son[p][x]=nq,p=fa[p];

             }

         }

     }

     void Init()

     {

         int len=strlen(s+);

         for (int i=; i<=cnt; ++i) wt[step[i]]++;

         for (int i=; i<=len; ++i) wt[i]+=wt[i-];

         for (int i=cnt; i>=; --i) od[wt[step[i]]--]=i;

         for (int i=cnt; i>=; --i) right[fa[od[i]]]+=right[od[i]];

     }

     void Solve()

     {

         for (int i=; i<=cnt; ++i)

         if (right[i]==)

         {

             SGT[].Update(,,n,End[i]-step[i]+,End[i]-step[fa[i]],End[i]+);

             SGT[].Update(,,n,End[i]-step[fa[i]],End[i],step[fa[i]]+);

         }

         for (int i=; i<=n; ++i)

         {

             Ans=0x7fffffff;

             SGT[].Query(,,n,i); Ans-=i;

             SGT[].Query(,,n,i);

             printf("%d\n",Ans);

         }

     }

 }SAM;

 int main()

 {

     scanf("%s",s+);

     n=strlen(s+);

     for (int i=; i<=n; ++i)

         SAM.Insert(s[i]-'a',i);

     SAM.Init();

     SAM.Solve();

 }

巴特西