题意：给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串.注意本质相同的子串多次出现算多次,如1 1 aaa这组数据答案为6,贡献1WA.代码里有些部分是为了处理子串本质不同,可能没删干净.
因为字符串的总长不超过10^5,那么后缀的个数也不超过10^5。一个长为x的后缀可以产生x个子串，其中在至少k个串中出现的子串一定是长度从1 开始递增的连续几个.那么对每个后缀可以二分找出最多能够产生多么长的在至少k个串中出现的子串.把所有串连起来求后缀数组，二分一个长度mid之后可以找出有哪些后缀和当前后缀的lcp>=mid,那么长度为mid的子串就可以在这些位置出现(即这些后缀所在的字符串包含了这个长度为mid的子串)。这些后缀一定是排名连续的一段区间，预处理每个后缀属于哪个字符串，判断这段区间中出现的不同的归属种数是否大于等于k，那么主席树（参考HH的项链）就可以做了。时间复杂度O(nlog^2n)=O(跑得出)。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=200005; int str[maxn];int tot=0; int tmp[2][maxn],sum[maxn],key[maxn];int sa[maxn],rank[maxn],height[maxn]; int st[maxn][20],qlog[maxn]; void getsa(int n,int m){int i,j,k,p,*rk=tmp[0],*res=tmp[1];for(i=0;i<m;++i)sum[i]=0;for(i=0;i<n;++i)sum[rk[i]=str[i]]++;for(i=1;i<m;++i)sum[i]+=sum[i-1];for(i=n-1;i>=0;--i){sa[--sum[rk[i]]]=i;}for(j=1,p=0;p<n;j<<=1,m=p){for(i=0;i<m;++i)sum[i]=0;for(p=0,i=n-j;i<n;++i)res[p++]=i;for(i=0;i<n;++i)if(sa[i]>=j)res[p++]=sa[i]-j;for(i=0;i<n;++i)sum[key[i]=rk[res[i]]]++;for(i=1;i<m;++i)sum[i]+=sum[i-1];for(i=n-1;i>=0;--i)sa[--sum[key[i]]]=res[i];for(res[sa[0]]=0,p=1,i=1;i<n;++i)res[sa[i]]=(rk[sa[i]]==rk[sa[i-1]]&&rk[sa[i]+j]==rk[sa[i-1]+j])?p-1:p++;swap(res,rk);}for(i=1;i<n;++i)rank[sa[i]]=i;for(i=0,k=0;i<n-1;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];str[j+k]==str[i+k];++k);for(int i=1;i<n;++i)st[i][0]=height[i];for(int j=1;(1<<j)<n;++j){for(int i=1;i<n;++i){st[i][j]=st[i][j-1];if(i+(1<<j-1)<n&&st[i+(1<<j-1)][j-1]<st[i][j])st[i][j]=st[i+(1<<j-1)][j-1];}}for(int j=0;(1<<j)<n;++j)qlog[1<<j]=j;for(int i=3;i<n;++i)if(!qlog[i])qlog[i]=qlog[i-1]; } int lcp(int a,int b){if(a==b)return 0x7f7f7f7f;a=rank[a];b=rank[b];if(a>b)swap(a,b);a++;int j=qlog[b-a+1];return min(st[a][j],st[b-(1<<j)+1][j]); } char buf[maxn]; int len[maxn],sumlen[maxn]; int belong[maxn]; struct node{int sum;node* ch[2];node(){}node(int x){sum=x;ch[0]=ch[1]=0;} }t[maxn*35];int szoftree=0; node* newnode(int x){t[++szoftree]=node(x);return t+szoftree; } void Insert(node* rt0,node* &rt,int l,int r,int k){rt=newnode(rt0->sum+1);if(l==r)return;int mid=(l+r)>>1;if(k<=mid){Insert(rt0->ch[0],rt->ch[0],l,mid,k);rt->ch[1]=rt0->ch[1];}else {Insert(rt0->ch[1],rt->ch[1],mid+1,r,k);rt->ch[0]=rt0->ch[0];} } int query(node* rt0,node* rt1,int l,int r,int ql,int qr){if(ql>qr)return 0;if(ql<=l&&r<=qr)return rt1->sum-rt0->sum;int mid=(l+r)>>1,ans=0;if(ql<=mid)ans+=query(rt0->ch[0],rt1->ch[0],l,mid,ql,qr);if(qr>mid) ans+=query(rt0->ch[1],rt1->ch[1],mid+1,r,ql,qr);return ans; } int last[maxn]; node* root[maxn]; typedef long long ll; ll ans[maxn]; int lastsuf[maxn]; int pos; int binary2(int l,int r,int x){while(l<=r){int mid=(l+r)>>1;if(lcp(pos,sa[mid])>=x)r=mid-1;else l=mid+1;}return r+1; } int binary3(int l,int r,int x){while(l<=r){int mid=(l+r)>>1;if(lcp(pos,sa[mid])>=x)l=mid+1;else r=mid-1;}return l-1; } int n,k; int binary1(int suf,int l,int r){pos=sa[suf];while(l<=r){int mid=(l+r)>>1;int left=binary2(1,suf,mid),right=binary3(suf,tot,mid);//printf("%d %d %d\n",suf,left,right);if(query(root[left-1],root[right],1,tot,1,left)>=k)l=mid+1;else r=mid-1;}return l-1; } bool vis[maxn]; int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;++i){scanf("%s",buf);len[i]=strlen(buf);for(int j=0;j<len[i];++j){str[tot++]=buf[j];}str[tot++]=256+i;sumlen[i]=tot;}str[tot++]=0;getsa(tot,256+n+1);for(int i=1;i<=n;++i){for(int j=sumlen[i-1];j<sumlen[i]-1;++j)belong[rank[j]]=i;}root[0]=t+0;root[0]->ch[0]=root[0]->ch[1]=t+0;root[0]->sum=0;for(int i=1;i<tot;++i){root[i]=root[i-1];if(belong[i]){Insert(root[i],root[i],1,tot,last[belong[i]]+1);last[belong[i]]=i;}}//printf("tot==%d\n",tot);for(int i=1;i<tot;++i){if(belong[i]){//printf("%d\n",sa[i]);int lo=1,hi=sumlen[belong[i]]-sa[i]-1;//长度上下界// if(vis[belong[i]]){//printf("!");// lo=max(lo,lcp(lastsuf[belong[i]],sa[i])+1);// }// lastsuf[belong[i]]=sa[i];vis[belong[i]]=true;hi=binary1(i,lo,hi);//printf("%d %d\n",lo,hi);ans[belong[i]]+=(hi-lo+1);}}for(int i=1;i<=n;++i)printf("%lld ",ans[i]);return 0; }