AC自动机建立fail树后树上DP
# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <algorithm>
# include <queue>
# define IL inline
# define RG register
# define ll long long
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
return x * z;
}
const int MAXN(1010);
struct AC{
int fail, ch[3], num;
} tree[MAXN];
int n, cnt, k, f[MAXN][MAXN], ans;
char t[MAXN];
queue <int> Q;
IL void Insert(){
RG int len = strlen(t), x = 0;
for(RG int i = 0; i < len; i++){
if(!tree[x].ch[t[i] - 'A']) tree[x].ch[t[i] - 'A'] = ++cnt;
x = tree[x].ch[t[i] - 'A'];
}
tree[x].num++;
}
IL void Bfs(){
while(!Q.empty()) Q.pop();
for(RG int i = 0; i < 3; i++)
if(tree[0].ch[i]) Q.push(tree[0].ch[i]);
while(!Q.empty()){
RG int u = Q.front(); Q.pop();
for(RG int i = 0; i < 3; i++)
if(tree[u].ch[i]){
tree[tree[u].ch[i]].fail = tree[tree[u].fail].ch[i];
Q.push(tree[u].ch[i]);
}
else tree[u].ch[i] = tree[tree[u].fail].ch[i];
tree[u].num += tree[tree[u].fail].num;
}
}
int main(){
n = Read(); k = Read();
for(RG int i = 1; i <= n; i++){
scanf(" %s", t);
Insert();
}
Bfs();
Fill(f, -127); f[0][0] = 0;
for(RG int K = 1; K <= k; K++){
for(RG int i = 0; i <= cnt; i++)
for(RG int j = 0; j < 3; j++)
f[K][tree[i].ch[j]]=max(f[K][tree[i].ch[j]],f[K - 1][i] + tree[tree[i].ch[j]].num);
}
for(RG int i = 0; i <= cnt; i++)
ans = max(ans, f[k][i]);
printf("%d
", ans);
return 0;
}