题解

#include<bits/stdc++.h>
using namespace std;

int main() {
int p, n, m, k;
int dp[210][50];
int sum[210][210];
string s, a[10];
auto read = {
int date = 0, w = 1;
char c = 0;
while (c < '0' || c > '9') {
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
date = date * 10 + c - '0';
c = getchar();
}
return date * w;
};
auto check = [&](int l, int r) {
string x = s.substr(l, r - l + 1);
for (int i = 1; i <= n; i++)
if (x.find(a[i]) == 0)
return true;
return false;
};
string ch;
s += '0';
p = read();
k = read();
for (int i = 1; i <= p; i++) {
cin >> ch;
s += ch;
}

n = read();
m = s.length() - 1;
for (int i = 1; i <= n; i++)
    cin >> a[i];

for (int i = m; i >= 1; i--)
    for (int j = i; j >= 1; j--) {
        sum[j][i] = sum[j + 1][i];
        if (check(j, i)) sum[j][i]++;
    }

dp[0][0] = 0;
for (int i = 1; i <= k; i++)
    dp[i][i] = dp[i - 1][i - 1] + sum[i][i];
for (int i = 1; i <= m; i++)
    dp[i][1] = sum[1][i];
for (int i = 1; i <= m; i++)
    for (int j = 1; j <= k && j < i; j++)
        for (int l = j; l < i; l++)
            dp[i][j] = max(dp[i][j], dp[l][j - 1] + sum[l + 1][i]);

cout<<dp[m][k];
return 0;

}