题目链接
手写一下AC自动机（我可没说我之前不是手写的）
Trie上dp，每个点的贡献加上所有是他后缀的串的贡献，也就是这个点到根的fail链的和。
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXK = 1010;
const int MAXN = 1010;
struct ACA{
int next[5], num, fail;
}AC[MAXN];
int f[MAXK][MAXN];
int n, k, cnt, ans;
char a[30];
queue <int> q;
void insert(){
int len = strlen(a + 1), p = 0, w;
for(int i = 1; i <= len; ++i){
w = a[i] - 'A';
if(!AC[p].next[w])
AC[p].next[w] = ++cnt;
p = AC[p].next[w];
}
++AC[p].num;
}
void build(){
int now;
for(int i = 0; i < 3; ++i)
if(AC[0].next[i])
q.push(AC[0].next[i]);
while(q.size()){
now = q.front(); q.pop();
for(int i = 0; i < 3; ++i)
if(AC[now].next[i]){
AC[AC[now].next[i]].fail = AC[AC[now].fail].next[i];
q.push(AC[now].next[i]);
}
else AC[now].next[i] = AC[AC[now].fail].next[i];
AC[now].num += AC[AC[now].fail].num;
}
}
void dp(){
for(int i = 0; i <= k; ++i)
for(int j = 1; j <= cnt; ++j)
f[i][j] = -2147483647;
for(int i = 1; i <= k; ++i)
for(int j = 0; j <= cnt; ++j){
for(int k = 0; k < 3; ++k)
f[i][AC[j].next[k]] = max(f[i][AC[j].next[k]], f[i - 1][j] + AC[AC[j].next[k]].num);
}
for(int i = 1; i <= cnt; ++i)
ans = max(ans, f[k][i]);
}
int main(){
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i){
scanf("%s", a + 1);
insert();
}
build();
dp();
printf("%d
", ans);
return 0;
}