bzoj1396

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1396

题目大意：

题解：后缀自动机，只出现一次，那么就是right值为1，那么对于一段1----L----R来说，（L----R)为一个最短识别子串对于（1----L-1）则可以用R-i+1来更新，对于（L---R）则可以用R-L+1来更新，那么两个线段树来维护即可。

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #define maxn 100005

 using namespace std;

 char s[maxn];

 int n,m,tot,root;

 bool v[maxn*];

 struct data{

     int last,son[maxn*][],val[maxn*],fa[maxn*];

     void prepare(){root=last=tot=;}

     int newnode(int x){val[++tot]=x; return tot;}

     void extend(int x)

     {

         int p=last,np=newnode(val[p]+); last=np;

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

         if (!p) fa[np]=root;

         else

         {

             int q=son[p][x];

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

             else

             {

                 int nq=newnode(val[p]+);

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

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

                 for (; p && son[p][x]==q; p=fa[p]) son[p][x]=nq;

              }

          }

     }

     void build ()

     {

         for (int i=; i<=n; i++) extend(s[i]-'a');

     }

     void whoisfather()

     {

         for (int i=; i<=tot; i++) v[fa[i]]=;

     }

 }SAM;

 struct T{

     int mn[maxn*];

     T(){memset(mn,0x3f,sizeof(mn));}

     void insert(int z,int l,int r,int x,int y,int w){

         if(l>y||r<x) return;

         if(l>=x&&r<=y){mn[z]=min(mn[z],w);return;}

         int mid=(l+r)>>;

         insert(z*,l,mid,x,y,w); insert(z*+,mid+,r,x,y,w);

     }

     int query(int z,int l,int r,int x){

         if(l==r&&l==x) return mn[z];

         int mid=(l+r)>>;

         if(x<=mid) return min(mn[z],query(z*,l,mid,x));

         else return min(mn[z],query(z*+,mid+,r,x));

     }

 }f,t;

 int main()

 {

     scanf("%s",s+); n=strlen(s+);

     SAM.prepare();

     SAM.build();

     SAM.whoisfather();

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

     {

         if (!v[i])

         {

             int l=SAM.val[i]-SAM.val[SAM.fa[i]],r=SAM.val[i];

             f.insert(,,n,l,r,r-l+);

             if (l>) t.insert(,,n,,l-,r);

         }

     }

     for (int i=; i<=n; i++) printf("%d\n",min(f.query(,,n,i),t.query(,,n,i)-i+));

 }

注：oyzx神犇清早刷神题，我就只能默默写渣渣题。