题目描述
上一题 最短编辑距离 的应用题,
增加了多次匹配,
动态规划
时间复杂度
时间复杂度为 O(len1*len2 *n*m
)
其中 len1 len2 为字符串长度, 不超过 10,接近 $10^8$
参考文献
算法基础课
Java 代码
import java.io.*;
import java.util.*;
public class Main{
static int n,m;
static int N=20;
static String[] strs;
static int[][]dp=new int[N][N];
static char[] w1,w2;
public static int findMinDist(String word1,String word2){
// 初始化
for(int[]f:dp){
Arrays.fill(f,0);
}
w1=word1.toCharArray();
w2=word2.toCharArray();
int len1=w1.length;
int len2=w2.length;
for(int i=0;i<=len1;i++){
dp[i][0]=i;
}
for(int j=0;j<=len2;j++){
dp[0][j]=j;
}
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(w1[i-1]==w2[j-1]){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
}
}
}
return dp[len1][len2];
}
public static void main(String[] args) throws IOException {
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String[] s2n=reader.readLine().split(" ");
n=Integer.parseInt(s2n[0]);
m=Integer.parseInt(s2n[1]);
strs=new String[n];
for(int i=0;i<n;i++){
strs[i]=reader.readLine();
}
String str;
int cnt;
int res;
while(m-->0){
s2n=reader.readLine().split(" ");
str=s2n[0];
cnt=Integer.parseInt(s2n[1]);
res=0;
for(int i=0;i<n;i++){
if(cnt>=findMinDist(strs[i],str)){
res++;
}
}
System.out.println(res);
}
}
}