应该是一个很基础的 ACAM 上 dp。
首先建出 ACAM。然后对于 ACAM 上的每一个节点，为其后缀的组合技数量等于在其 fail 树上直到根的路径上有 tag 的节点的数量。于是直接在 ACAM 上 dp 即可。
#include <bits/stdc++.h>
#define llong long long
#define N 305
#define K 1005
using namespace std;char a[N];
int son[N][4], fail[N], tag[N], tsiz = 1;
int dp[K][N];
int n, k, l, ans;int que[N], he, ta;int main(){scanf("%d %d", &n, &k);for(int i = 1; i <= n; ++i){scanf("%s", a+1), l = strlen(a+1);int x = 1;for(int j = 1; j <= l; ++j){if(!son[x][a[j]^64]) son[x][a[j]^64] = ++tsiz;x = son[x][a[j]^64];}++tag[x];}for(int i = 1; i <= 3; ++i){if(son[1][i]) fail[son[1][i]] = 1, que[++ta] = son[1][i];else son[1][i] = 1;}while(he <= ta){int x = que[he++];tag[x] += tag[fail[x]];for(int i = 1; i <= 3; ++i){if(son[x][i]) fail[son[x][i]] = son[fail[x]][i], que[++ta] = son[x][i];else son[x][i] = son[fail[x]][i];}}for(int i = 0; i <= k; ++i)for(int j = 1; j <= tsiz; ++j)dp[i][j] = -1e9-7;dp[0][1] = 0;for(int i = 0; i < k; ++i)for(int j = 1; j <= tsiz; ++j)for(int k = 1; k <= 3; ++k)dp[i+1][son[j][k]] = max(dp[i+1][son[j][k]], dp[i][j]+tag[son[j][k]]);for(int i = 1; i <= tsiz; ++i)ans = max(ans, dp[k][i]);printf("%d", ans);return 0;
}