本来想做点英语作业的。想10分钟把这题搞定的。结果傻了去写trie树dp又傻了没有考虑终点也可以有子结点。
我真是无药可救了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tcnt;
struct trie_node {
int d, e, t[26];
inline trie_node(int d0 = 0) {
e = 0;
d = d0 + 1;
memset(t, 0, sizeof(t));
}
inline int ins(char c) {
if (!t[c - 97])
t[c - 97] = ++ tcnt;
return t[c - 97];
}
inline int trans(char c) {
return t[c - 97];
}
};
const int inf = 0x3f3f3f3f;
const int maxs = 15009;
const int maxl = 309;
int n, l, trt, f[2][maxs];
char a[maxl], tmp[maxl];
trie_node tr[maxs];
void trieIns(char* a) {
int p = trt;
for (; *a; ++ a)
p = tr[p]. ins(*a);
tr[p]. e = 1;
}
int dp() {
int cur = 0, prv = 1;
memset(f, 0x3f, sizeof(f));
f[cur][trt] = 0;
for (int i = 0; i < l; ++ i) {
swap(cur, prv);
for (int j = 1; j <= tcnt; ++ j)
f[cur][j] = inf;
for (int j = 1; j <= tcnt; ++ j)
if (f[prv][j] < inf) {
f[cur][j] = min(f[cur][j], f[prv][j] + 1);
int tmp = tr[j]. trans(a[i]);
if (tmp) {
if (tr[tmp]. e)
f[cur][trt] = min(f[cur][trt], f[prv][j]);
f[cur][tmp] = min(f[cur][tmp], f[prv][j]);
}
}
}
return f[cur][trt];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d%s", &n, &l, a);
trt = 1;
tcnt = 1;
for (int i = 0; i < n; ++ i) {
scanf("%s", tmp);
trieIns(tmp);
}
printf("%d\n", dp());
}