Light OJ 1314 Names for Babies

http://www.lightoj.com/volume_showproblem.php?problem=1314

题意:给定一个串和p,q，求长度在p到q之间的子串有几种

思路:后缀数组，对于每个位置的贡献是min(n-sa[i],q)，然后要减去重复和没有的部分，就是max(height[i],p-1)，当然，还要对0取个max

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 char s[];

 int num[],sa[],rank[],h[],p,q,n;

 int ws[],wa[],wb[],wv[];

 int read(){

     int t=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void solve(){

     int ans=;

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

      ans+=std::max(,std::min(q,n-sa[i])-std::max(p-,h[i]));

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

 }

 bool cmp(int *r,int a,int b,int l){

     return r[a]==r[b]&&r[a+l]==r[b+l];

 }

 void da(int *r,int *sa,int n,int m){

     int *x=wa,*y=wb,*t,i,j,p;

     for (i=;i<n;i++) x[i]=r[i];

     for (i=;i<m;i++) ws[i]=;

     for (i=;i<n;i++) ws[x[i]]++;

     for (i=;i<m;i++) ws[i]+=ws[i-];

     for (i=n-;i>=;i--) sa[--ws[x[i]]]=i;

     for (j=,p=;p<n;m=p,j*=){

         for (p=,i=n-j;i<n;i++) y[p++]=i;

         for (i=;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;

         for (i=;i<n;i++) wv[i]=x[y[i]];

         for (i=;i<m;i++) ws[i]=;

         for (i=;i<n;i++) ws[wv[i]]++;

         for (i=;i<m;i++) ws[i]+=ws[i-];

         for (i=n-;i>=;i--) sa[--ws[wv[i]]]=y[i];

         for (t=x,x=y,y=t,i=,x[sa[]]=,p=;i<n;i++)

          x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

     }

 }

 void cal(int *r,int n){

     int i,j,k=;

     for (i=;i<=n;i++) rank[sa[i]]=i;

     for (i=;i<n;h[rank[i++]]=k)

      for (k?k--:,j=sa[rank[i]-];r[i+k]==r[j+k];k++);

 }

 int main(){

     int T=read(),Tcase=;

     while (T--){

         Tcase++;printf("Case %d: ",Tcase);

         scanf("%s",s);

         p=read();q=read();

         n=strlen(s);

         for (int i=;i<n;i++) num[i]=s[i];

         num[n]=;

         da(num,sa,n+,);

         cal(num,n);

         solve();

     }

 }