记录编号	250656	评测结果	AAAAAAAAAA
题目名称	字符串	最终得分	100
用户昵称	debug	是否通过	通过
代码语言	C++	运行时间	2.556 s
提交时间	2016-04-15 16:52:32	内存使用	8.03 MiB

#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
char f[222222];int siz;int n,m;int tot=-1;int top=0;
struct ff{int x,y,z,num,siz;}e[222222]={};int tot2=0;
struct gg{int x,y,num,num2;}g[222222]={};int temp=n;
int q[222222]={};int ans[222222]={};bool vis[222222]={};
bool cmp1(gg a,gg b){return a.x<b.x;}
bool cmp2(gg a,gg b){return a.y<b.y;}
void slove1(){
	for(int i=1;i<=n;i++)
	{
		scanf("%s",f);
		siz=strlen(f);
		printf("%lld\n",1LL*siz*(siz+1)/2);
	}
}
void slove()
{
	int cnt=1;int pos=0;
	vis[g[0].num]=1;
	for(int i=1;i<=top;i++)
	{
		if(g[i].x!=g[i-1].x)
		{
			if(cnt<m)//当前字符不够用
				for(int j=pos;j<i;j++)
					g[j].x=2147483647,g[j].y=2147483647,vis[g[j].num]=0;
			else
				for(int j=pos;j<i;j++)
					ans[g[j].num]++,vis[g[j].num]=0;
			cnt=0;pos=i;
		}
		if(!vis[g[i].num])
			vis[g[i].num]=1,cnt++;
	}
	if(cnt<m)//当前字符不够用
		for(int j=pos;j<=top;j++)
			g[j].x=2147483647,vis[g[j].num]=0;
	else
		for(int j=pos;j<=top;j++)
			ans[g[j].num]++,vis[g[j].num]=0;
	return;
}
int main()
{
	freopen("stringa.in","r",stdin);
	freopen("stringa.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(m==0)
	{slove1();return 0;}
	for(int ii=1;ii<=n;ii++)
	{
		scanf("%s",f);
		siz=strlen(f);
		for(int i=0;i<siz;i++)
			e[++tot].x=f[i]-'a',e[tot].num=ii,e[tot].siz=siz;
	}
	for(int i=0;i<=tot;i++)
		g[i].x=e[i].x,g[i].num2=i,g[i].num=e[i].num;
	top=tot;
	sort(g,g+top+1,cmp1);
	slove();
	for(int k=1;k<=tot;k++)
	{
		for(int i=0;i<=top;i++)
			if(g[i].num!=e[g[i].num2+k].num||g[i].x==2147483647)//已经不在当前的字符串上，废掉||已经废掉
				g[i].y=2147483647,g[i].x=2147483647;
			else
				g[i].y=g[i].x*27+e[g[i].num2+k].x;
		sort(g,g+top+1,cmp2);
		g[0].x=1;
		for(int i=1;i<=top;i++)
			if(g[i].y==g[i-1].y)
				g[i].x=g[i-1].x;
			else
				g[i].x=g[i-1].x+1;
		while(top>=0)
			if(g[top].y==2147483647)top--;
			else break;
		slove();
		if(top<0)break;
	}
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}