由于是多个串，还与每个子串的信息有关，很容易想到用 SA 或广义 SAM。这里选择用 SA。
首先先把字符串转化为数组，连接起来，中间用一些不会出现的数。处理出后缀数组与 \(height\) 数组，下面简写为 \(h\)。
所以我们转化后实际上就是求一个后缀中有多长的前缀在 \(k\) 个来源不同串的后缀的前缀出现过，答案贡献即为前缀的长度。
对于一个区间 \((l,r)\) 包含了 \(k\) 个不同的串中的后缀，那么这些串有公共的长度为 \(\min(h_i)\hspace{0.1cm}(l<i\le r)\) 的公共前缀。
可以证明，如果有两个区间 \((l_1,r_1)\)，\((l_2,r_2)\)，且 \(l_1\ge l_2\)，\(r1 \le r2\)，那么 \(\min(h_i)>\min(h_j)\hspace{0.1cm}(l_1<i\le r_1,l_2<j\le r_2)\)，因为具有单调性。
所以只有刚好包含 \(k\) 个来源不同串中的后缀时，才会对这个后缀贡献答案。
那么我们就可以用单调队列维护这个区间，当这个区间达到 \(k\) 个来源不同串的后缀时，我们将左端点往右推，并且更新答案，区间最小值用单调队列维护。然而如果多个区间包含一个点，那么求的应该是最大值，因为长度大的符合条件，那么小的也符合条件，那求最大值有很多求法，但线段树一定是最无脑的，所以直接选择线段树。
一个易错点，对于相同的右端点，不能只用最小的包含 \(k\) 个来源不同串的后缀的区间更新，因为这样会让这个区间左边的点无法更新到答案，在缩短区间前且满足为 \(k\) 个时，可能对于他们这个区间最小则是这个，而如果回退了就不能照顾这些点对应的最小区间（简单来说就是有些值更新不到），所以要边回退边更新。
时间复杂度：\(O(n\times \log(n))\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
int T,kt,a[N],b[N],rk[N],sa[N],cnt[N],n,p[N],h[N],vis[N],laz[4*N],f[4*N],sp[N],c[N];
long long ans[N];
char s[N];
deque<pii>q;
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
inline void pushup(int x)
{
f[x]=max(f[ls(x)],f[rs(x)]);
}
inline void fix(int x,int l,int r,int k)
{
f[x]=max(f[x],k);
laz[x]=max(laz[x],k);
}
inline void pushdown(int x,int l,int r)
{
int mid=(l+r)>>1;
fix(ls(x),l,mid,laz[x]);
fix(rs(x),mid+1,r,laz[x]);
laz[x]=0;
}
void update(int x,int l,int r,int nl,int nr,int k)
{
if(l>=nl&&r<=nr)
{
f[x]=max(f[x],k);
laz[x]=max(laz[x],k);
return;
}
pushdown(x,l,r);
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid,nl,nr,k);
if(mid<nr)update(rs(x),mid+1,r,nl,nr,k);
pushup(x);
}
void getans(int x,int l,int r)
{
if(l==r)
{
//cout<<l<<" "<<sa[l]<<" "<<p[sa[l]]<<" "<<f[x]<<endl;
ans[p[sa[l]]]+=f[x];
return;
}
pushdown(x,l,r);
int mid=(l+r)>>1;
getans(ls(x),l,mid);
getans(rs(x),mid+1,r);
}
signed main()
{
scanf("%lld%lld",&T,&kt);
int m=26;
for(int i=1;i<=T;i++)
{
scanf("%s",s+1);
int len=strlen(s+1);
for(int j=1;j<=len;j++)a[++n]=s[j]-'a',p[n]=i,sp[n]=a[n];
for(int j=n-len+1;j<=n;j++)c[j]=n-j+1;
a[++n]=i+26,sp[n]=a[n],m=i+26;
if(kt==1)printf("%lld ",len*(len+1)/2);
}
if(kt==1)return 0;
sp[n+1]=2e9;
for(int i=1;i<=n;i++)cnt[a[i]]++;
for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--)sa[cnt[a[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int num=0;
for(int i=n-k+1;i<=n;i++)b[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)b[++num]=sa[i]-k;
for(int i=0;i<=m;i++)cnt[i]=0;
for(int i=1;i<=n;i++)cnt[a[i]]++;
for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--)sa[cnt[a[b[i]]]--]=b[i];
swap(a,b);
a[sa[1]]=1;
num=1;
for(int i=2;i<=n;i++)
{
if(b[sa[i]]==b[sa[i-1]]&&b[sa[i]+k]==b[sa[i-1]+k])a[sa[i]]=num;
else a[sa[i]]=++num;
}
if(num==n)break;
m=num;
}
int r=0;
//for(int i=1;i<=n;i++)cout<<sa[i]<<" ";
//cout<<endl;
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1;i<=n;i++)
{
if(rk[i]==1)continue;
if(r)r--;
int j=sa[rk[i]-1];
while(j+r<=n&&i+r<=n&&sp[i+r]==sp[j+r])++r;
h[rk[i]]=r;
//cout<<i<<" "<<r<<endl;
}
int sum=0,l=1;
for(int i=1;i<=n;i++)
{
if(!vis[p[sa[i]]])sum++;
vis[p[sa[i]]]++;
while(!q.empty()&&q.back().second>=h[i])q.pop_back();
q.push_back({sa[i],h[i]});
while(sum>=kt)
{
if(!q.empty()&&sa[l]==q.front().first)q.pop_front();
update(1,1,n,l,i,q.front().second);
if(sum==kt&&vis[p[sa[l]]]==1)break;
vis[p[sa[l]]]--;
if(!vis[p[sa[l]]])sum--;
l++;
}//cout<<l<<" "<<i<<" "<<sum<<" "<<c[sa[i]]<<" "<<q.front().second<<endl;
}
getans(1,1,n);
for(int i=1;i<=T;i++)printf("%I64d ",ans[i]);
return 0;
}
/*
2 2
aaab
aaababa
*/