题解：P2432 zxbsmk爱查错
cbcyh
·
·
题解
还算简单的dp题。
题意
给定一个长度为 \texttt{L} 的字符串和有 \texttt{M} 个单词的词典，要求从字符串中删除尽可能少的字符，使得删完后字符串是由词典里的单词连续拼接成的。
思路
考虑只有 1 维的 \texttt{dp}。
状态：
###### 转移：
从 $i$ 这个位置出发，主动去更新。
$f_x \leftarrow f_i + (x - i - len_j)$。
在这条转移中，我们选择了下一个单词是词典中的第 $j$ 个单词，$x$ 是 $i$ 之后第一个出现的第 $j$ 个单词的结尾位置。$(i,x]$ 这段区间长度为 $x-i$，需要保留 $len_j$ 个字符，即需要删除 $x - i - len_j$ 个字符。
那么问题来了，怎样寻找 $x$ 呢？
可以记 $nxt_{i,j}$ 表示 $i$ 这个位置后面（不包括 $i$)，第一个 $j$ 出现的位置。这个可以 $O(L)$ 预处理。具体实现：从 $L$ 到 $1$ 遍历，期间维护 $lst$ 数组来记到当前每个字母最后一个出现的位置。那么 $nxt_i$ 就是 $lst$，但要注意不要把 $i$ 也算进 $nxt_i$。
这样，我们就能找到 $x$。令 $j$ 一开始为 $i$，假设现在匹配到了第 $k$ 个单词的第 $l$ 个字符，那么 $j \leftarrow nxt_{i,t_{k,l}}$。注意特判找不到的情况。
说起来挺复杂，但其实代码没这么难。
## 时空复杂度
###### 时间复杂度：
输入、预处理是 $O(L\times v+len)$。$len$ 是字典中单词长度的和，$v$ 是字母的个数，也就是 $26$。
$\texttt{dp}$ 的时间复杂度是 $O(L\times len)$ 的。$len$ 的含义同上。
所以，总的时间复杂度是 $O(L \times (v+len))$。
###### 空间复杂度：
这个就很简单了，$O(L \times v+len)$。
## 代码实现
[AC link](https://www.luogu.com.cn/record/253261636)
```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 700, M = 310, V = 30;
int test, n, m, len[N], nxt[M][V], lst[V], f[M];
//f[i] 表示只考虑前i个字母，且i是最后一个被保留的字母，这样的情况下最少删除几个字母
char s[N], t[N][V];
ll ans = 0ll;
inline void solve () {
ans = 0ll;
scanf("%d%d%s", &n, &m, s + 1);
for (int i = 1; i <= n; i++) {
scanf("%s", t[i] + 1);
len[i] = strlen(t[i] + 1);
}
for (int i = 1; i <= 26; i++) {
lst[i] = m + 1;
}
for (int i = m; i >= 0; i--) {
memcpy(nxt[i], lst, sizeof(nxt[i]));
lst[s[i] - 'a' + 1] = i;
//注意先memcpy再更新lst！！
}
for (int i = 1; i <= m; i++) {
f[i] = m; //初始全为无穷大
}
f[0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 1; j <= n; j++) {
int x = i;
for (int k = 1; k <= len[j]; k++) {
x = nxt[x][t[j][k] - 'a' + 1]; //寻找x
if (x == m + 1) {
break;
}
}
if (x == m + 1) {
continue;
}
f[x] = min(f[x], f[i] + (x - i) - len[j]);
}
}
ans = (ll)(1e18);
for (int i = 0; i <= m; i++) {
ans = min(ans, 1ll * f[i] + m - i); //f[i]只考虑了前i位，所以后面m - i位需要删除
}
printf("%lld\n", ans);
return;
}
int main() {
solve();
return 0;
}
```