算法 - 编辑距离

2020-08-05 10:11:32

来源： https://www.acwing.com/problem/content/901/

描述：

给定n个长度不超过10的字符串以及m次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式
第一行包含两个整数n和m。

接下来n行，每行包含一个字符串，表示给定的字符串。

再接下来m行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过10。

编辑距离是最短编辑距离的应用，只是有些地方时是C++的一些应用，状态方程都是一样的。但是在理一遍，加清思路分析。

动态规划，线性dp分析：

状态表示f[i][j]:

  • 集合：表示a[1 ~ i] 变成 b[1 ~ j]所需要的代价
  • 属性： min

状态计算:

  • 添加： 添加之前的是b[j],所以添加之前，需要a[i]和b[j - 1]进行匹配。 所以就是f[i]][j - 1] + 1
  • 删除： 删除之后a[i]和b[j]相等，所以删除后是f[i - 1][j], 那么f[i - 1][j] + 1 就是f[i][j]
  • 修改： a[i - 1]和b[j - 1]都相等，那么看a[i]和b[j]，如果相等 + 0，不等 + 1

所以状态转移方程就是：

$f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + 1 / 0 )$

注意就是C++的字符串的一些用法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 1010, M = 15;
char w[N][M];
int f[M][M];
int n, m;

int edit(char a[], char b[]) {
    // 从a + 1, b + 1开始统计a, b两个字符串的长度
    int la = strlen(a + 1), lb = strlen(b + 1);

    for(int i = 1; i <= lb; i++) f[0][i] = i;
    for(int i = 1; i <= la; i++) f[i][0] = i;

    for(int i = 1; i <= la; i++)
        for(int j = 1; j <= lb; j++) {
        f[i][j] = min(f[i][j - 1], f[i - 1][j]) + 1;
        f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }

    return f[la][lb];
}


int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%s", w[i] + 1);

    while(m--) {
    char tmp[M];
    int limit;
    scanf("%s%d", tmp + 1, &limit);

    int res = 0;
    for(int i = 1; i <= n; i++)
        if (edit(w[i], tmp) <= limit) res ++;

    cout << res << endl;
    }

    return 0;
}