记录编号	250694	评测结果	AAAAAAAAAA
题目名称	字符串	最终得分	100
用户昵称	_Horizon	是否通过	通过
代码语言	C++	运行时间	0.343 s
提交时间	2016-04-15 17:49:23	内存使用	49.34 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 200010
using namespace std;

int n, k;
char s[maxn];
int in[maxn], out[maxn];

struct Node{
	int len, link, nxt[27];
}st[maxn << 1];
int root, size, last;

void init(){
	last = root = size = 0;
	st[root].link = -1;
	st[root].len = 0;
}

void Extend(int c){
	int p = last, q = st[p].nxt[c];
	if(q){
		if(st[q].len == st[p].len + 1)
		    last = q;
		else{
			int clone = ++ size;
			st[clone] = st[q];
			st[clone].len = st[p].len + 1;
			for(; ~p && st[p].nxt[c] == q; p = st[p].link)
			    st[p].nxt[c] = clone;
			st[q].link = clone;
			last = clone;
		}
		return;
	}
	int cur = ++ size;
	st[cur].len = st[p].len + 1;
	for(; ~p && st[p].nxt[c] == 0; p = st[p].link)
	    st[p].nxt[c] = cur;
	if(p == -1)
		st[cur].link = root;
	else{
		int q = st[p].nxt[c];
		if(st[q].len == st[p].len + 1)
		    st[cur].link = q;
		else{
			int clone = ++ size;
			st[clone] = st[q];
			st[clone].len = st[p].len + 1;
			for(; ~p && st[p].nxt[c] == q; p = st[p].link)
			    st[p].nxt[c] = clone;
			st[cur].link = st[q].link = clone;
		}
	}
	last = cur;
}

int vis[maxn];

int total_vis[maxn];
void update(int rt, int y){
	while(~rt){
		if(vis[rt] == y)break;
		total_vis[rt] ++;
		vis[rt] = y;
		rt = st[rt].link;
	}
}


long long val[maxn];
long long dfs(int rt){
	if(vis[rt])return val[rt];
	vis[rt] = true;
	long long ret = 0;
	if(~st[rt].link)ret = dfs(st[rt].link);
	if(total_vis[rt] >= k)
		ret += (long long)st[rt].len - (st[rt].link == -1 ? 0 : st[st[rt].link].len);
	return val[rt] = ret;
}

int main(){
	freopen("stringa.in", "r", stdin);
	freopen("stringa.out", "w", stdout);
	init();
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i ++){
		in[i] = out[i-1] + 1;
		scanf("%s", s+in[i]);
		out[i] = strlen(s+in[i]) + in[i] - 1;

		last = root;
		for(int j = in[i]; j <= out[i]; j ++)
		    Extend(s[j] - 'a');
	}

	for(int i = 1; i <= n; i ++){
		int now = root;
		for(int j = in[i]; j <= out[i]; j ++)
		    now = st[now].nxt[s[j] - 'a'], update(now, i);
	}
	memset(vis, 0, sizeof vis);
	for(int i = 1; i <= n; i ++){
		long long ans = 0;
		int now = root;
		for(int j = in[i]; j <= out[i]; j ++){
			now = st[now].nxt[s[j] - 'a'];
			ans += dfs(now);
		}
		printf("%lld ", ans);
	}
	return 0;
}