后缀数组
Orz zyf 神题不会做啊，先坑着吧……sigh
//BZOJ 3473
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-')r=-;
for(; isdigit(ch);ch=getchar()) v=v*+ch-'';
return r*v;
}
const int N=1e5+,INF=~0u>>;
/*******************template********************/
int sa[N],rank[N],height[N],belong[N],ans[N];
int wa[N],wb[N],c[N],n,q,a[N];
bool cmp(int *r,int a,int b,int l){
return r[a]==r[b] && r[a+l]==r[b+l];
}
void DA(int *s,int *sa,int n,int m){
int i,j,p,*x=wa,*y=wb;
rep(i,m) c[i]=;
rep(i,n) c[x[i]=s[i]]++;
F(i,,m-) c[i]+=c[i-];
D(i,n-,) sa[--c[x[i]]]=i;
for(j=,p=;p<n;j<<=,m=p){
for(p=,i=n-j;i<n;i++) y[p++]=i;
rep(i,n) if (sa[i]>=j) y[p++]=sa[i]-j; rep(i,m) c[i]=;
rep(i,n) c[x[y[i]]]++;
F(i,,m-) c[i]+=c[i-];
D(i,n-,) sa[--c[x[y[i]]]]=y[i];
swap(x,y); p=; x[sa[]]=;
F(i,,n-) x[sa[i]]=cmp(y,sa[i-],sa[i],j) ? p- : p++;
}
}
void calheight(int *s,int *sa,int n){
int k=;
F(i,,n) rank[sa[i]]=i;
rep(i,n){
if (k) k--;
int j=sa[rank[i]-];
while(s[i+k]==s[j+k]) k++;
height[rank[i]]=k;
}
}
char s[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("3473.in","r",stdin);
freopen("3473.out","w",stdout);
#endif
n=getint(); q=getint()-;
int l=;
F(i,,n){
scanf("%s",s+l);
l=strlen(s);
s[l++]='a'-;
}
rep(i,l) a[i]=s[i]-'a'+;
l--;
DA(a,sa,l+,);
calheight(a,sa,l);
ST();
int tmp=;
rep(i,l){
if (s[i]<){tmp++;continue;}
belong[rank[i]]=tmp;
}
int t=,k=;
F(i,,l) if(belong[i]){
if (!cnt[belong[i]]) k++;
cnt[belong[i]]++;
if (k<=q){
for(;k-(cnt[belong[t]]==)>=q; k-=(cnt[belong[t]]==), --cnt[belong[t++]]);
rec[i]=t;
}
}
F(i,,n){
LL ans=; int k=;
F(j,
return ;
}
3473: 字符串
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 121 Solved: 53
[Submit][Status][Discuss]
Description
给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串？
Input
第一行两个整数n，k。
接下来n行每行一个字符串。
Output
一行n个整数，第i个整数表示第i个字符串的答案。
Sample Input
3 1
abc
a
ab
abc
a
ab
Sample Output
6 1 3
HINT
对于 100% 的数据，1<=n，k<=10^5，所有字符串总长不超过10^5，字符串只包含小写字母。