編輯距離

題目

給定 $n$個(gè)長度不超過 $10$ 的字符串以及 $m$ 次詢問，每次詢問給出一個(gè)字符串和一個(gè)操作次數(shù)上限。

對于每次詢問，請你求出給定的$n$個(gè)字符串中有多少個(gè)字符串可以在上限操作次數(shù)內(nèi)經(jīng)過操作變成詢問給出的字符串。

每個(gè)對字符串進(jìn)行的單個(gè)字符的插入、刪除或替換算作一次操作。

詳見899. 編輯距離 - AcWing題庫

輸入格式

第一行包含兩個(gè)整數(shù)$n$和$m$。

接下來 $n$ 行，每行包含一個(gè)字符串，表示給定的字符串。

再接下來 $m$ 行，每行包含一個(gè)字符串和一個(gè)整數(shù)，表示一次詢問。

字符串中只包含小寫字母，且長度均不超過 $10$。

輸出格式

輸出共$m$行，每行輸出一個(gè)整數(shù)作為結(jié)果，表示一次詢問中滿足條件的字符串個(gè)數(shù)。

// input:
3 2
abc
acd
bcd
ab 1
acbd 2
// output:
1
3

題解

總的思路就是對于在每次詢問中將每個(gè)序列的最少編輯距離得出，在分別與操作次數(shù)上限相比即可：

#include <iostream>
#include <cstring>
using namespace std;int n, m, f[1005][1005], len_1[1005], len_2, t;
char a[1005][1005], b[1005];int main()
{cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];len_1[i] = strlen(a[i]); }while(m --){int cnt = 0;cin >> b >> t;len_2 = strlen(b); for(int k = 1; k <= n; k++){for(int i = 0; i <= len_1[k]; i++) f[i][0] = i;for(int j = 0; j <= len_2; j++) f[0][j] = j;for(int i = 1; i <= len_1[k]; i++)for(int j = 1; j <= len_2; j++){f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[k][i - 1] != b[j - 1]));}if(f[len_1[k]][len_2] <= t) cnt++;}cout << cnt << endl;}return 0;
}