AcWing 899. 编辑距离
原题链接
简单
作者:
MoonlightF
,
2023-11-28 08:57:12
,
所有人可见
,
阅读 46
import java.util.Scanner;
public class Main{
static int N = 15, M = 1010;
static String[] str = new String[M];
static int[][] f = new int[N][N];
static int edit_distance(String s1,String s2){
int la = s1.length();
int lb = s2.length();
char[] a = new char[la + 1];
char[] b = new char[lb + 1];
for(int i = 1; i <= la; i ++)a[i] = s1.charAt(i-1);
for(int i = 1; i <= lb; i ++)b[i] = s2.charAt(i-1);
for(int i = 0; i <= lb; i ++)f[0][i] = i;
for(int i = 0; i <= la; i ++)f[i][0] = i;
for(int i = 1; i <= la; i ++){
for(int j = 1; j <= lb; j ++){
f[i][j] = Math.min(f[i-1][j] + 1,f[i][j - 1] + 1);
if(a[i] == b[j]) f[i][j] = Math.min(f[i][j],f[i - 1][j - 1]);
else f[i][j] = Math.min(f[i][j],f[i - 1][j - 1] + 1);
}
}
return f[la][lb];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i = 0; i < n; i ++){
str[i] = sc.next();
}
while(m-- > 0){
String s = sc.next();
int limit = sc.nextInt();
int res = 0;
for(int i = 0; i < n; i ++){
if(edit_distance(str[i],s) <= limit) res++;
}
System.out.println(res);
}
}
}