bzoj3277-串

Code

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<string>
using namespace std;
#define rep(i,l,r) for(register int i=(l);i<=(r);++i)
#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
#define il inline
typedef long long ll;
typedef double db;

//---------------------------------------
const int nsz=1e5+50,ndsz=2*nsz,csz=27;
int n,k,sz[nsz];
string s[nsz];

//sam
struct tnd{int ch[csz],l,fa;}sam[ndsz];
#define ch(p,c) sam[p].ch[c]
#define fa(p) sam[p].fa 
int rt=1,ps=1,las=1;
void insert(int c){
	int p=las;
	las=++ps,sam[las].l=sam[p].l+1;
	for(;p&&ch(p,c)==0;p=fa(p))ch(p,c)=las;
	if(p==0)fa(las)=1;
	else{
		if(sam[ch(p,c)].l==sam[p].l+1)fa(las)=ch(p,c);
		else{
			int q=ch(p,c),q1=++ps;
			sam[q1]=sam[q];
			sam[q1].l=sam[p].l+1;
			fa(q)=fa(las)=q1;
			for(;p&&ch(p,c)==q;p=fa(p))ch(p,c)=q1;
		}
	}
}

int c[ndsz],seq[ndsz];
void gettp(){
	rep(i,1,ps)++c[sam[i].l];
	rep(i,1,ps)c[i]+=c[i-1];
	rep(i,1,ps)seq[c[sam[i].l]--]=i;
}

int tm[ndsz],vi[ndsz],sum[ndsz],ans[nsz];

void gettm(){
	rep(i,1,n){
		int cur=rt,v;
		rep(j,0,sz[i]-1){
			v=cur=ch(cur,s[i][j]-'a');
			while(v&&vi[v]!=i)++tm[v],vi[v]=i,v=fa(v);
		}
	}
}

void sol(){
	gettp();
	gettm();
	rep(i,1,ps)sum[i]=(tm[i]>=k?sam[i].l-sam[fa(i)].l:0);
	rep(i,1,ps)sum[seq[i]]+=sum[fa(seq[i])];
	rep(i,1,n){
		int ans=0,cur=rt;
		rep(j,0,sz[i]-1){
			cur=ch(cur,s[i][j]-'a');
			ans+=sum[cur];
		}
		::ans[i]=ans;
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>k;
	rep(i,1,n){
		cin>>s[i];
		sz[i]=s[i].length();
		las=1;
		rep(j,0,sz[i]-1)insert(s[i][j]-'a');
	}
	sol();
	rep(i,1,n)cout<<ans[i]<<' ';
	cout<<'
';
	
	return 0;
}