题目思路：求长度不小于k的公共子串的个数，做法是维护一个单调栈，详见论文。
[cpp] #include #include #include #include #include #include #include #include #include //#include #include using namespace std; #define inf 0x3f3f3f3f #define M 210000 int max(int a,int b) { return a>b a:b; } int min(int a,int b) { return a } struct node { int num,h; }q[M]; int rank[M],sa[M],height[M]; int ta[M],tb[M],tv[M],ts[M],r[M],sum; bool cmp(int *y,int a,int b,int l) { return y[a]==y[b]&&y[a+l]==y[b+l]; } void da(int n,int m) { int i,j,p; int *x=ta,*y=tb; for(i=0;i for(i=0;i for(i=1;i for(i=n-1;i>=0;i--) sa[--ts[x[i]]]=i; for(j=1,p=1;p { p=0; for(i=n-j;i for(i=0;i=j) y[p++]=sa[i]-j; for(i=0;i for(i=0;i for(i=0;i for(i=1;i for(i=n-1;i>=0;i--) sa[--ts[tv[i]]]=y[i]; swap(x,y); x[sa[0]]=0; p=1; for(i=1;i { if(cmp(y,sa[i-1],sa[i],j)) x[sa[i]]=p-1; else x[sa[i]]=p++; } } } void calh(int n) { int i,k,tmp; for(i=1;i<=n;i++) rank[sa[i]]=i; k=0; for(i=0;i { tmp=sa[rank[i]-1]; for(;r[i+k]==r[tmp+k];k++) ; height[rank[i]]=k; k --k:0; } } __int64 solve(int len1,int n,int k) { int top=0,tail=0,i; __int64 sum=0; __int64 ans=0; node tmp; if(sa[1] { tmp.h=height[2]; tmp.num=1; sum+=tmp.h-k+1; q[tail++]=tmp; // printf("i %d sum %I64d ans %I64d\n",1,sum,ans); } for(i=2;i<=n;i++) { if(height[i] { top=0,tail=0,sum=0; if(sa[i] { tmp.h=height[i+1]; tmp.num=1; sum=height[i+1]-k+1; q[tail++]=tmp; } // printf("i %d sum %I64d ans %I64d\n",i,sum,ans); continue; } if(sa[i] { tmp.num=1; tmp.h=height[i+1]; sum+=tmp.h-k+1; while(top=height[i+1]) { sum-=(q[tail-1].h-tmp.h)*q[tail-1].num; tmp.num+=q[tail-1].num; tail--; } q[tail++]=tmp; // printf("i %d sum %I64d ans %I64d\n",i,sum,ans); } else if(sa[i]>len1) { ans+=sum; // puts("akkk"); if(i==n) continue; tmp.num=0; tmp.h=height[i+1]; while(top=height[i+1]) { sum-=(q[tail-1].h-tmp.h)*q[tail-1].num; tmp.num+=q[tail-1].num; tail--; } if(tmp.num) q[tail++]=tmp; // printf("i %d sum %I64d ans %I64d\n",i,sum,ans); } } top=tail=0; sum=0; if(sa[1]>len1) { tmp.h=height[2]; tmp.num=1; sum+=tmp.h-k+1; q[tail++]=tmp; // printf("i %d sum %I64d\n",1,sum); } for(i=2;i<=n;i++) { if(height[i] { top=0,tail=0,sum=0; if(sa[i]>len1) { tmp.h=height[i+1]; tmp.num=1; sum=tmp.h-k+1; q[tail++]=tmp; } // printf("i %d sum %I64d\n"