求条

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
#define int long long
#define all(x) x.begin(), x.end()

inline void cmax(int &x, const int &y) {((x < y) ? x = y : 1);}
inline void cmin(int &x, const int &y) {((x > y) ? x = y : 1);}

const int MAXN = 1000 + 5;

struct ACAM{
    int trie[MAXN][26], val[MAXN], fail[MAXN], vis[MAXN];
    int cnt = 0;

    void insert(string a) {
        int u = 0;
        for(int i = 0; i < a.size(); ++i) {
            int &v = trie[u][a[i] - 'A'];
            if(!v) v = ++cnt;
            u = v;
        }
        ++val[u];
    }

    void build() {
        queue<int> q;
        for(int i = 0; i < 26; ++i)
            if(trie[0][i]) q.push(trie[0][i]);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = 0; i < 26; ++i) {
                int &v = trie[u][i];
                if(v) {
                    fail[v] = trie[fail[u]][i];
                    val[v] += val[fail[v]];
                    q.push(v);
                } else {
                    v = trie[fail[u]][i];
                }
            }
        }
    }
    
    int calc(int u) {
        int ret = 0;
        while(u) ret += val[u], u = fail[u];
        return ret;
    }
} trie, trie2;

int dp[MAXN][MAXN / 2];
int vis[MAXN][MAXN / 2];

void solve() {
    memset(dp, -0x3f, sizeof(dp));
dp[0][0] = 0;
memset(vis, 0, sizeof vis), vis[0][0] = 1;
    int n, k; cin >> n >> k;
    string s;
    for(int i = 1; i <= n; i ++) cin >> s, trie.insert(s);
    trie.build();
    for(int i = 0; i < k; i ++) {
        for(int j = 0; j <= trie.cnt; j ++) {
        	if(vis[i][j] == 0) continue;
            for(int k = 0; k < 3; k ++){
                int json = trie.trie[j][k];
                cmax(dp[i + 1][json], trie.calc(json) + dp[i][j]);
                vis[i + 1][json] = 1;
            }
        }
    }
    int maxn = -2e9;
    for(int i = 0; i <= trie.cnt; i ++) cmax(maxn, dp[k - 1][i]);
    cout << maxn << "\n";
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}