分析

我们考虑 上的 ，定义 为，匹配了 个字符，当前在 节点的最大价值。那么转移为 那么，现在的问题就在于如何求出 数组。由于 指针指向的是最长后缀，所以有 的转移，这个可以在构造 指针时就构造好。那么总的复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 100;
int f[N][N],fail[N],ch[N][3],val[N],size;
int n,m;
void insert(char *S) {
    int len = strlen(S + 1),u = 0;
    for(int i = 1;i <= len;i++) {
        int c = (S[i] - 'A');
        if(!ch[u][c]) ch[u][c] = ++size;
        u = ch[u][c];
    }val[u]++;
}
void build() {
    queue<int> Q;
    for(int i = 0;i < 3;i++) if(ch[0][i]) Q.push(ch[0][i]);
    while(!Q.empty()) {
        int x = Q.front();Q.pop();
        for(int i = 0;i < 3;i++) {
            int y = ch[x][i];
            if(y) {fail[ch[x][i]] = ch[fail[x]][i];val[y] += val[fail[y]];Q.push(y);}
            else ch[x][i] = ch[fail[x]][i];
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) {
        static char S[N];scanf("%s",S + 1);insert(S);
    }
    build();memset(f,-0x3f,sizeof(f)); 
    for(int i = 0;i < 3;i++) f[1][ch[0][i]] = val[ch[0][i]];
//    for(int i = 1;i <= size;i++) cout << val[i] << endl;
    for(int i = 2;i <= m;i++) {
        for(int j = 1;j <= size;j++) {
            for(int k = 0;k < 3;k++) {
                f[i][ch[j][k]] = max(f[i][ch[j][k]],f[i-1][j] + val[ch[j][k]]);
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= size;i++) ans = max(ans,f[m][i]);
    cout << ans << endl;return 0;
}