关于 $O(|T|^3)$ 50pts

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N1=5050,SG=30;
struct trie{
    int trie[N1<<4][SG];
    int cnt[N1<<4];
    int tot=1;
    void ins(string s){
        int len=s.length();
        int now=1;cnt[now]++;
        for(int i=0;i<len;i++){
            int id=s[i]-'a';
            if(!trie[now][id]) trie[now][id]=++tot;
            now=trie[now][id];cnt[now]++;
        }
    }
}trie;
int f[N1][N1];
ll g[N1];
int n,K;int sub;
void slv1(){//1-6
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        trie.ins(s);
    }string t;cin>>t;
    int len=t.length();t=' '+t;
    for(int i=1;i<=len;i++){
        for(int j=1;j<=len;j++){
            if(j+i-1>len) break;
            int lp=j,rp=j+i-1;
            int now=1;int v=0x3f3f3f3f;
            for(int k=lp;k<=rp;k++){
                now=trie.trie[now][t[k]-'a'];
                if(now==0) break;
                v=min(v,f[k+1][rp]+1);
            }f[lp][rp]=v;
            //cout<<lp<<' '<<rp<<' '<<f[lp][rp]<<endl;
        }
    }ll ans=0;
    for(int i=1;i<=len;i++){
        for(int j=i;j<=len;j++){
            int cnt=max(K-f[i][j]+1,0);
            g[i]+=cnt;g[j+1]-=cnt;ans+=cnt;
        }
    }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;
}