这里是一种建广义(SAM)的新姿势，就是每次都把(last)置成(1)
看起来也没什么科学的地方，但是这就是建广义(SAM)的方法
之后我们对于那些新插入的位置我们给它涂上颜色
显然对于一个出现次数超过(k)次的子串，其子树内部必然有超过(k)种颜色
我们来一遍(hh)的项链就可以统计出来所有节点子树内部的颜色个数了
之后对于每一个串的每一个前缀我们统计其出现次数超过(k)的后缀
由于知道这个后缀前缀的结尾，我们直接树上倍增就好了，一直往上跳颜色次数小于(k)的节点，最后再跳一次就是了
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define maxn 200005
#define re register
#define LL long long
#define lowbit(x) ((x)&(-x))
int lst=1,cnt=1,n,K,num,__;
struct E{int v,nxt;}e[maxn];
struct Ask{int x,y,rk;}a[maxn];
std::vector<int> pos[maxn>>1];
char S[maxn>>1]; int c[maxn],pre[maxn>>1];
int fa[maxn],len[maxn],son[maxn][26],t[maxn],sz[maxn],to[maxn];
int deep[maxn],lg2[maxn],_to[maxn],val[maxn],head[maxn],f[maxn][20];
inline int cmp(Ask A,Ask B) {return A.y<B.y;}
inline void add_(int x,int y){e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
inline void add(int x,int val){for(re int i=x;i<=cnt;i+=lowbit(i)) c[i]+=val;}
inline int ask(int x){int now=0;for(re int i=x;i;i-=lowbit(i)) now+=c[i];return now;}
void dfs(int x) {
to[x]=++__,_to[__]=x;sz[x]=1;
for(re int i=head[x];i;i=e[i].nxt) deep[e[i].v]=deep[x]+1,dfs(e[i].v),sz[x]+=sz[e[i].v];
}
inline void ins(int c,int o)
{
int p=++cnt,f=lst; lst=p;
len[p]=len[f]+1,t[p]=o;pos[o].push_back(p);
while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
int x=son[f][c];
if(len[f]+1==len[x]) {fa[p]=x;return;}
int y=++cnt;
len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;
for(re int i=0;i<26;i++) son[y][i]=son[x][i];
while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
int main()
{
scanf("%d%d",&n,&K);
for(re int i=1;i<=n;i++)
{
scanf("%s",S+1);
int L=strlen(S+1);lst=1;
for(re int j=1;j<=L;j++) ins(S[j]-'a',i);
}
for(re int i=2;i<=cnt;i++) add_(fa[i],i); deep[1]=1,dfs(1);
for(re int i=1;i<=cnt;i++) a[i].rk=i,a[i].x=to[i],a[i].y=to[i]+sz[i]-1;
std::sort(a+1,a+cnt+1,cmp); int now=1;
for(re int i=1;i<=cnt;i++)
{
if(t[_to[i]])
{
if(pre[t[_to[i]]]) add(pre[t[_to[i]]],-1);
add(i,1),pre[t[_to[i]]]=i;
}
while(a[now].y==i) val[a[now].rk]=ask(a[now].y)-ask(a[now].x-1),now++;
}
for(re int i=1;i<=cnt;i++) f[i][0]=fa[i];
for(re int i=2;i<=cnt;i++) lg2[i]=lg2[i>>1]+1;
for(re int j=1;j<=lg2[cnt];j++)
for(re int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1];
for(re int i=1;i<=n;i++)
{
LL ans=0;
for(re int j=0;j<pos[i].size();j++)
{
int T=pos[i][j];
for(re int k=lg2[deep[T]];k>=0;k--)
if(val[f[T][k]]<K&&f[T][k]) T=f[T][k];
if(val[T]<K) T=fa[T];
ans+=len[T];
}
printf("%lld ",ans);
}
return 0;
}