好久没有写博客了，好惭愧啊……虽然这是一道弱题但还是写一下吧。
这道题目的思路应该说是很容易形成：字符串+最大值？自然联想到学过的AC自动机与DP。对于给定的字符串建立出AC自动机，dp状态dp[i][j]则表示第i位（我们求的字符串的第i位），匹配到自动机的第j位所能获得的最大值。只需要沿儿子节点与fail指针转移即可。
#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
int n, m, ans, cnt;
int dp[maxn][maxn], ch[maxn][], tag[maxn * ], fail[maxn * ];
string s; void Gmax(int &x, int y)
{
if(y > x) x = y;
} void Trie_Ins()
{
int len = s.length(), now = ;
for(int i = ; i < len; i ++)
{
if(!ch[now][s[i] - 'A']) ch[now][s[i] - 'A'] = ++ cnt;
now = ch[now][s[i] - 'A'];
}
tag[now] += ;
} void AC_Build()
{
queue <int> q;
for(int i = ; i < ; i ++)
if(ch[][i]) q.push(ch[][i]);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = ; i < ; i ++)
{
if(ch[u][i])
{
fail[ch[u][i]] = ch[fail[u]][i];
tag[ch[u][i]] += tag[fail[ch[u][i]]];//注意不是加1哦
q.push(ch[u][i]);
}
else ch[u][i] = ch[fail[u]][i];
}
}
} void DP()
{
dp[][] = ;
for(int i = ; i <= m; i ++)
for(int j = ; j <= cnt; j ++)
{
if(dp[i - ][j] == -) continue;
for(int k = ; k < ; k ++)
{
if(ch[j][k]) Gmax(dp[i][ch[j][k]], dp[i - ][j] + tag[ch[j][k]]);
else Gmax(dp[i][fail[ch[j][k]]], dp[i - ][j] + tag[fail[ch[j][k]]]);
}
}
} int main()
{
scanf("%d%d", &n, &m);
memset(dp, -, sizeof(dp));
for(int i = ; i <= n; i ++)
{
cin >> s;
Trie_Ins();
}
AC_Build();
DP();
for(int i = ; i <= cnt; i ++) ans = max(ans, dp[m][i]);
printf("%d\n", ans);
return ;
}