赛时 70pts 没调完，最后只写了 50pts。
下文中 T_{[a,a-1]} 表示空串（其中 T 是字符串，a\le|T|）。
这里稍微改一下前缀的定义（为方便叙述）：
字符串 R' 是字符串 R 的前缀当且仅当存在 \color{red}{0\le p\le|R|} 且 p 为整数使得 R'=R_{[1,p]}。
15pts
首先，发现三元组的个数是 O(|T|^2K) 的，考虑暴力枚举三元组，但此时不好 chk。
那如何 chk 呢。考虑 DP，设 f_{l,r,k} 表示 (l,r,k) 是否合法，转移时枚举新加的串的位置即可，复杂度 O(n^4)。（不过这个东西貌似可以bitset优化，可能能过 30）
30pts
发现一个状态表示一个 bool 十分浪费，考虑优化。发现若 f_{l,r,k} 合法，则可以通过添加空串的方式使 f_{l,r,k+1} 合法，可以设 f_{l,r} 表示使 (l,r,k) 合法的最小 k 值，就有转移 f_{l,r}=\min_{l<i\le r+1}(f_{i,r})+1（要求 T_{[l,i-1]}是某个 S_i 的前缀）。
判断前缀可以使用哈希，复杂度 O(n|T|^3)，用 trie 则为 O(|T|^3)。（实际上加剪枝后在原题数据中可以拿 50pts）
50pts
考虑优化转移，上文中合法的 i 构成了一段区间，此时可以预处理出 to_i 表示最大的 j 使 T_{[i,j]} 是某个 S_i 的前缀（因为 T_{[i,i-1]} 是空串，故 j 一定存在）。
此时 i 的上界为 \min(to_l,r)+1。由于对查 f_{i,r} 而言，左端点是递减的，可以使用单调栈上二分，复杂度 O(|T|^2\log|T|)。
70pts
此时状态数会炸，考虑将状态与 K 挂钩。
发现对于 l,k 来说，使 (l,r,k) 合法的 r 构成一段区间，考虑交换状态和答案，记 f_{l,k} 表示使 (l,r,k) 合法的最大的 r。
转移如下：
其中 $f_{i,1}=to_i$。方便起见，可设 $f_{|T|+1,1}=|T|$。
转移就相当于 RMQ，可以 ST 表维护。
如何求 $to_i$ 呢，注意到 $to_i$ 具有可二分性，使用字符串哈希 chk 即可。
答案为 $\sum\limits_{i=1}^{|T|}\sum\limits_{j=1}^Kf_{i,j}+1-i$。
下面考虑第二问，每一个 $f$ 值对答案的贡献形如区间加等差数列，将其变为在二重差分数组上单点改，最后还原即可。
复杂度 $O(K|T|+n|T|\log|T|)$。
### 100pts
发现 max 里面 $k$ 那一维是 1，能不能依此优化？
可以的，记 $tr_{i,j}$ 表示区间 $[i,j]$ 中使 $to_i$ 取最大值的 $i$。可以将转移过程大致抽象为：
1.对当前区间求 $tr$。
2.更新 $r$ 为 $to_{tr}$ 并转移到 $k+1$。
此时，我们发现，$[l,tr-1]$ 的 $to$ 值一定不会成为 max。
修改 $tr$ 定义，设 $tr_i$ 表示 $[i,to_i+1]$ 中使 $to_i$ 取最大值的 $i$。
依此建 $tr_i\rightarrow i$ 的边，发现建出来的是根节点为自环的外向“森林”，转移到 $k+1$ 就相当于跳父亲（定义根节点父亲为自身）。
设当前在点 $u$，则所对 $f$ 值为 $to_u$。
我们求出 $s_u$ 表示 $\sum\limits_{i=1}^Kf_{u,i}$。$v_u$ 表示有多少个 $f$ 值跳到了 $u$，前者可以树上倍增，后者可以树上差分求，可以依据这两个东西来做第二问，依据 $s$ 做第一问。
综上，本题在 $O(n|T|\log|T|)$ 的时间复杂度内得到解决。
### 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
const int N1=5050,N=5e5+10,SG=30;
int n,K;int sub;
int to[N];
int hs[12][N],ln[12],pb[N];
int base=131,mod=1011451423;
int hsh[N];
int gh(int l,int r){
return (hsh[r]-1ll*pb[r-l+1]*hsh[l-1]%mod+mod)%mod;
}ll g[N];
int tr[N];
struct segtree{
pii T[N<<2];
#define ls p*2
#define rs p*2+1
#define mid (l+r)/2
void pu(int p){
T[p]=max(T[ls],T[rs]);
}
void bd(int p,int l,int r){
if(l==r){
T[p]=mk(to[l],-l);return ;
}bd(ls,l,mid);bd(rs,mid+1,r);pu(p);
}pii qry(int p,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return T[p];
pii res=mk(-1,0);
if(pl<=mid) res=max(res,qry(ls,l,mid,pl,pr));
if(pr>mid) res=max(res,qry(rs,mid+1,r,pl,pr));
return res;
}
#undef ls
#undef rs
#undef mid
}sgt;
vector<int> E[N];
int dep[N];
int fa[N][22];ll sm[N][22];
bool vis[N];
ll val[N],sum[N],tg[N];
void dfs(int u,int pr){
vis[u]=1;dep[u]=dep[pr]+1;
fa[u][0]=pr;sm[u][0]=to[u];
for(int i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1],sm[u][i]=sm[u][i-1]+sm[fa[u][i-1]][i-1];
for(auto v:E[u]) if(!vis[v]) dfs(v,u);
}void dfs2(int u){
vis[u]=1;
for(auto v:E[u]){
if(!vis[v]) dfs2(v),val[u]+=val[v];
}
}
void slv1(){
cin>>n>>K;
for(int i=1;i<=n;i++){
string s;cin>>s;
ln[i]=s.length();
int hsh=0;
for(int j=0;j<ln[i];j++){
hsh=1ll*hsh*base%mod;
hsh=(hsh+s[j]-'a')%mod;
hs[i][j+1]=hsh;
}
}string t;cin>>t;
int len=t.length();
t=' '+t;
for(int i=1;i<=len;i++){
hsh[i]=1ll*hsh[i-1]*base%mod+t[i]-'a';
hsh[i]%=mod;
}pb[0]=1;for(int i=1;i<=len;i++) pb[i]=1ll*pb[i-1]*base%mod;
for(int i=1;i<=len;i++){
int l=i-1,r=len;
while(l<r){
int mid=(l+r+1)/2;
int hsh1=gh(i,mid),lenn=mid-i+1,cnt=0;
for(int j=1;j<=n;j++){
if(lenn>ln[j]) continue;
if(hsh1==hs[j][lenn]) cnt++;
}
if(cnt>0) l=mid;
else r=mid-1;
}to[i]=l;
}to[len+1]=len;
sgt.bd(1,1,len+1);
for(int i=1;i<=len;i++) tr[i]=-sgt.qry(1,1,len+1,i,to[i]+1).se;
for(int i=1;i<=len;i++) E[tr[i]].push_back(i);
for(int i=len;i>=1;i--) if(!vis[i]) dfs(i,i);
ll ans=0;
for(int i=1;i<=len;i++){
ll s=0;int now=i;
for(int j=19;j>=0;j--){
if((K>>j)&1) s+=sm[now][j],now=fa[now][j];
}ans+=s;sum[i]=s;
if(dep[i]>K){
val[i]++,val[now]--;
}else{
val[i]++,val[now]--;tg[now]+=K-(dep[i]-1);
}vis[i]=0;sum[i]+=K;sum[i]-=1ll*K*i;
//cout<<i<<' '<<now<<endl;
}
ans+=1ll*len*K;ans-=1ll*K*(1ll*len*(len+1)/2);
for(int i=len;i>=1;i--) if(!vis[i]) dfs2(i);
for(int i=1;i<=len;i++){
val[i]+=tg[i];//cout<<i<<' '<<val[i]<<' '<<dep[i]<<endl;
g[i+1]-=K;g[i]+=sum[i];g[i+1]-=sum[i];g[to[i]+2]+=val[i];
}
for(int i=1;i<=len;i++) g[i]+=g[i-1];
for(int i=1;i<=len;i++) g[i]+=g[i-1];
cout<<ans<<endl;for(int i=1;i<=len;i++) cout<<g[i]<<' ';
}
int main(){
cin>>sub;
slv1();
return 0;
}
```