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
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 char s[200005]; 7 int num[200005],sa[200005],rank[200005],h[200005],p,q,n; 8 int ws[200005],wa[200005],wb[200005],wv[200005]; 9 int read(){ 10 int t=0,f=1;char ch=getchar(); 11 while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} 12 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 13 return t*f; 14 } 15 void solve(){ 16 int ans=0; 17 for (int i=1;i<=n;i++) 18 ans+=std::max(0,std::min(q,n-sa[i])-std::max(p-1,h[i])); 19 printf("%d ",ans); 20 } 21 bool cmp(int *r,int a,int b,int l){ 22 return r[a]==r[b]&&r[a+l]==r[b+l]; 23 } 24 void da(int *r,int *sa,int n,int m){ 25 int *x=wa,*y=wb,*t,i,j,p; 26 for (i=0;i<n;i++) x[i]=r[i]; 27 for (i=0;i<m;i++) ws[i]=0; 28 for (i=0;i<n;i++) ws[x[i]]++; 29 for (i=1;i<m;i++) ws[i]+=ws[i-1]; 30 for (i=n-1;i>=0;i--) sa[--ws[x[i]]]=i; 31 for (j=1,p=1;p<n;m=p,j*=2){ 32 for (p=0,i=n-j;i<n;i++) y[p++]=i; 33 for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j; 34 for (i=0;i<n;i++) wv[i]=x[y[i]]; 35 for (i=0;i<m;i++) ws[i]=0; 36 for (i=0;i<n;i++) ws[wv[i]]++; 37 for (i=1;i<m;i++) ws[i]+=ws[i-1]; 38 for (i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i]; 39 for (t=x,x=y,y=t,i=1,x[sa[0]]=0,p=1;i<n;i++) 40 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 41 } 42 } 43 void cal(int *r,int n){ 44 int i,j,k=0; 45 for (i=1;i<=n;i++) rank[sa[i]]=i; 46 for (i=0;i<n;h[rank[i++]]=k) 47 for (k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); 48 } 49 int main(){ 50 int T=read(),Tcase=0; 51 while (T--){ 52 Tcase++;printf("Case %d: ",Tcase); 53 scanf("%s",s); 54 p=read();q=read(); 55 n=strlen(s); 56 for (int i=0;i<n;i++) num[i]=s[i]; 57 num[n]=0; 58 da(num,sa,n+1,200); 59 cal(num,n); 60 solve(); 61 } 62 }