记录编号	251097	评测结果	AAAAAAAAAA
题目名称	字符串	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	0.317 s
提交时间	2016-04-16 21:03:03	内存使用	26.35 MiB

/*
Problem:String;
Language:c++;
by dydxh;
Date:2016.04.16;
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<vector>
#include<ctime>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define ull unsigned long long
using namespace std;
const int oo=2000000000;
const int maxn=100005;
int n,K;
int S[maxn],T[maxn];
char Str[maxn];
struct Suffix_AutoMaton{
	int Last,Cnt;
	int Tor[maxn<<1][27],Val[maxn<<1],Par[maxn<<1];
	int Col[maxn<<1],Vis[maxn<<1];
	ll Num[maxn<<1];
	void Initialize(){Last=Cnt=1;}
	void Expand(int x){
		int p=Last,np=++Cnt;Val[np]=Val[p]+1;
		while(p && Tor[p][x]==0) Tor[p][x]=np,p=Par[p];
		if(p==0) Par[np]=1;
		else{
			int q=Tor[p][x];
			if(Val[q]==Val[p]+1) Par[np]=q;
			else{
				int nq=++Cnt;Val[nq]=Val[p]+1;
				memcpy(Tor[nq],Tor[q],sizeof(Tor[nq]));
				Par[nq]=Par[q],Par[np]=Par[q]=nq;
				while(p && Tor[p][x]==q) Tor[p][x]=nq,p=Par[p];
			}
		}
		Last=np;
	}
	void Color(int Now,int Sign){
		while(Now){
			if(Vis[Now]==Sign) break;
			Vis[Now]=Sign,Col[Now]++;
			Now=Par[Now];
		}
	}
	ll Finder(int x){
		if(x==0) return 0;
		if(Vis[x]) return Num[x];
		Vis[x]=1,Num[x]=Finder(Par[x]);
		if(Col[x]>=K) Num[x]+=Val[x]-Val[Par[x]];
		return Num[x];
	}
}Sam;
void Initialize(){
	Sam.Initialize();
	scanf("%d %d\n",&n,&K);
	for(int i=1;i<=n;i++){
		S[i]=T[i-1]+1;
		scanf("%s\n",Str+S[i]);
		T[i]=strlen(Str+S[i])+S[i]-1;
		Sam.Last=1;
		for(int j=S[i];j<=T[i];j++){
			if(Sam.Tor[Sam.Last][S[j]-'a'+1] && Sam.Val[Sam.Last]==j-S[i]+1)
				Sam.Last=Sam.Tor[Sam.Last][S[j]-'a'+1];
			else Sam.Expand(Str[j]-'a'+1);
		}
	}
}
void Colorful(){
	for(int i=1;i<=n;i++){
		int Now=1;
		for(int j=S[i];j<=T[i];j++){
			Now=Sam.Tor[Now][Str[j]-'a'+1];
			Sam.Color(Now,i);
		}
	}
	memset(Sam.Vis,0,sizeof(Sam.Vis));
}
int main(){
	freopen("stringa.in","r",stdin);
	freopen("stringa.out","w",stdout);
	Initialize();
	Colorful();
	for(int i=1;i<=n;i++){
		int Now=1;ll Ans=0;
		for(int j=S[i];j<=T[i];j++){
			Now=Sam.Tor[Now][Str[j]-'a'+1];
			Ans+=Sam.Finder(Now);
		}
		printf("%lld ",Ans);
	}
	printf("\n");
	//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
    return 0;
}