福州网站建设/百度投广告怎么收费

被SAM艹翻了，说一下SA的做法。
首先把串连起来跑SA，然后枚举枚举每个后缀，看看该后缀有几个前缀符合条件，即所在区间不同串的数目$\geq k$。我们可以预处理出$rec_i$表示$i$向左第一次出现$k$个不同串的位置。然后可以发现，对于每个后缀，如果$suffix(i)$有$j$个前缀合法，那么$suffix(i+1)$至少有$j-1$个前缀合法，每次二分左右端点判断，类似求$height$数组的求法可以在$O(nlogn)$的时间内完成这一过程。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#include<cstdlib>
#define N 300005
using namespace std;
int n,K,len;
int cc[N],t1[N],t2[N],sa[N],height[N],rank[N];
int f[N][20],rec[N],cnt[N],belong[N],st[N],en[N];
char s[N];
inline int read()
{int a=0,f=1; char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}return a*f;
}
inline bool cmp(int *y,int a,int b,int k)
{int arank1=y[a];int brank1=y[b];int arank2=a+k>=len?-1:y[a+k];int brank2=b+k>=len?-1:y[b+k];return arank1==brank1&&arank2==brank2;
}
inline void make_sa()
{int *x=t1,*y=t2;int m=256;for (int i=0;i<m;i++) cc[i]=0;for (int i=0;i<len;i++) ++cc[x[i]=s[i]];for (int i=1;i<m;i++) cc[i]+=cc[i-1];for (int i=len-1;~i;i--) sa[--cc[x[i]]]=i;for (int k=1;k<len;k<<=1){int p=0;for (int i=len-k;i<len;i++) y[p++]=i;for (int i=0;i<len;i++)if (sa[i]>=k) y[p++]=sa[i]-k;for (int i=0;i<m;i++) cc[i]=0;for (int i=0;i<len;i++) ++cc[x[y[i]]];for (int i=1;i<m;i++) cc[i]+=cc[i-1];for (int i=len-1;~i;i--) sa[--cc[x[y[i]]]]=y[i];swap(x,y); x[sa[0]]=0; m=1;for (int i=1;i<len;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?m-1:m++;if (m>=len) break;}
}
inline void make_height()
{for (int i=0;i<len;i++) rank[sa[i]]=i;height[0]=0;int k=0;for (int i=0;i<len;i++){if (!rank[i]) continue;if (k) k--;int j=sa[rank[i]-1];while (s[i+k]==s[j+k]) k++;height[rank[i]]=k;}
}
inline void make_st()
{for (int i=0;i<len;i++)f[i][0]=height[i];for (int j=1;j<=19;j++)for (int i=0;i<len;i++)if (i+(1<<j)-1<len)f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int rmq(int l,int r)
{int k=log2(r-l+1);return min(f[l][k],f[r-(1<<k)+1][k]);
}
inline bool judge(int x,int y)
{int L,R;if (height[x+1]<y) R=x;else{int l=x+1,r=len-1;while (l<=r){int mid=l+r>>1;if (rmq(x+1,mid)>=y) l=mid+1; else r=mid-1;}R=r;}if (height[x]<y) L=x;else{int l=0,r=x-1;while (l<=r){int mid=l+r>>1;if (rmq(mid+1,x)>=y) r=mid-1; else l=mid+1;}L=l;}return rec[R]>=L;
}
int main()
{n=read(); K=read(); len=-1;for (int i=1;i<=n;i++){st[i]=++len;scanf("%s",s+len);len=strlen(s);s[len]=' '; en[i]=len-1;}make_sa();make_height();make_st();for (int i=1;i<=n;i++)for (int j=st[i];j<=en[i];j++)belong[j]=i;int t=1,k=0;for (int i=0;i<len;i++)if (belong[sa[i]]){if (!cnt[belong[sa[i]]]) k++;cnt[belong[sa[i]]]++;if (k>=K){while (k-(cnt[belong[sa[t]]]==1)>=K){k-=(cnt[belong[sa[t]]]==1);cnt[belong[sa[t++]]]--;}rec[i]=t;}}for (int i=1;i<=n;i++){long long ans=0;int k=0;for (int j=st[i];j<=en[i];j++){if (k) k--;while (k+1<=en[i]-j+1&&judge(rank[j],k+1)) k++;ans+=k;}printf("%lld ",ans);}return 0;
}