记录编号	252372	评测结果	AAAAAAAAAA
题目名称	字符串	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.538 s
提交时间	2016-04-20 10:48:43	内存使用	52.39 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int SIZEN=100010;
typedef long long LL;
int N,K;
char str[SIZEN*2];
int in[SIZEN*2],out[SIZEN*2];
class poi
{
public:
	int son[26];
	int fa;
	LL len;
	void clear()
	{
		fa=len=0;
		memset(son,0,sizeof(son));
	}
};
int postot[SIZEN*4]={0};
int visit[SIZEN*4]={0};
class miku
{
public:
	int last,id;
	poi P[SIZEN*4];
	void clear()
	{
		last=id=0;
		P[id].clear();
	}
	int newnode()
	{
		id++;
		P[id].clear();
		return id;
	}
	void add(char a)
	{
		int c=a-'a';
		int end;
		int tmp=last;
		if(P[last].son[c])
		{
			end=P[last].son[c];
			if(P[end].len==P[tmp].len+1) 
			{
				last=end;
				return;
			}
			else
			{
				int np=newnode();
				P[np]=P[end];
				P[np].len=P[tmp].len+1;
				P[end].fa=np;
				for(;P[tmp].son[c]!=0&&P[tmp].son[c]==end;tmp=P[tmp].fa) P[tmp].son[c]=np;
				last=np;
			}
			return;
		}
		end=newnode();
		P[end].len=P[tmp].len+1;
		for(;tmp&&P[tmp].son[c]==0;tmp=P[tmp].fa) P[tmp].son[c]=end;
		if(P[tmp].son[c]==0) P[tmp].son[c]=end;
		else
		{
			int next=P[tmp].son[c];
			if(P[next].len==P[tmp].len+1) P[end].fa=next;
			else
			{
				int np=newnode();
				P[np]=P[next];
				P[np].len=P[tmp].len+1;
				P[end].fa=P[next].fa=np;
				for(;P[tmp].son[c]!=0&&P[tmp].son[c]==next;tmp=P[tmp].fa) P[tmp].son[c]=np;
			}
		}
		last=end;
	}
	void update(int x,int y)
	{
		while(x)
	    {
		    if(visit[x]==y) break;
			postot[x]++;
		    visit[x]=y;
			x=P[x].fa;
	    }
	}
	void check(int x)
	{
		cout<<"id:"<<x<<endl;
		cout<<P[x].len<<" "<<P[x].fa<<endl;
		for(int i=0;i<26;i++) if(P[x].son[i]) cout<<"to:"<<P[x].son[i]<<" "<<i<<endl;
		cout<<endl;
	}
}sam;
void read()
{
	scanf("%d%d",&N,&K);
	out[0]=-1;
	for(int i=1;i<=N;i++)
	{
		in[i]=out[i-1]+1;
		scanf("%s",str+in[i]);
		out[i]=strlen(str)-1;
		sam.last=0;
		for(int j=in[i];j<=out[i];j++) sam.add(str[j]);
	}
	//for(int i=0;i<=sam.id;i++)sam.check(i);
	/*for(int i=1;i<=N;i++)
	{
		cout<<in[i]<<" "<<out[i]<<endl;
		for(int j=in[i];j<=out[i];j++) cout<<str[j];
		cout<<endl;
	}*/
}
LL val[SIZEN*4]={0};
LL dfs(int x)
{
	if(visit[x]) return val[x];
	LL re=0;
	visit[x]=1;
	if(sam.P[x].fa) re=dfs(sam.P[x].fa);
	if(postot[x]>=K) re+=sam.P[x].len-sam.P[sam.P[x].fa].len;
	val[x]=re;
	//cout<<x<<endl;
	return val[x];
}
void work()
{
	for(int i=1;i<=N;i++)
	{
		int now=0;
		for(int j=in[i];j<=out[i];j++)
		{
			int c=str[j]-'a';
			now=sam.P[now].son[c];
			sam.update(now,i);
		}
	}
	memset(visit,0,sizeof(visit));
	for(int i=1;i<=N;i++)
	{
		int now=0;
		LL ans=0;
		for(int j=in[i];j<=out[i];j++)
		{
			int c=str[j]-'a';
			now=sam.P[now].son[c];
			ans+=dfs(now);
		}
		printf("%lld\n",ans);
	}
}
int main()
{
	freopen("stringa.in","r",stdin);
	freopen("stringa.out","w",stdout);
	sam.clear();
	read();
	work();
	return 0;
}