题意:n个串中有多少个能在规定的步数之内变成B字符串。
解法:编辑距离+枚举
编辑距离:http://blog.sina.com.cn/s/blog_6473891f0100grx6.html
一、问题描述
设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:
二、分析解答
设所给的两个字符串为A[1:m]和B[1:n]。定义D[i][j]=d(A[1:i],B[1,j])。单字符a,b间的距离定义为:
d(a,b)=0 (a=b)
d(a,b)=1(a!=b)
考察从字符串A[1:i]到字符串B[1:j]的变换。可分成以下几种情况:
(1)字符A[i]改为字符B[j];需要d(A[i],B[j])次操作。
(2)删除字符A[i];需要1次操作。
(3)插入字符B[j];需要1次操作。
因此,D[i][j]可递归地计算如下。
D[i][j]=min{D[i-1][j-1]+d(A[i],B[j]),D[i-1][j]+1,D[i][j-1]+1}
#include <vector> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <string> using namespace std; const int M=2005; int dp[M][M]; int dist(char a[],char b[]) { int n=strlen(a); int m=strlen(b); for(int i=0;i<n;i++) dp[i][0]=i; for(int j=0;j<m;j++) dp[0][j]=j; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int cst; if(a[i-1]==b[j-1]) cst=0; else cst=1; dp[i][j]=min(dp[i-1][j-1]+cst,dp[i-1][j]+1); dp[i][j]=min(dp[i][j],dp[i][j-1]+1); } } return dp[n][m]; } int main() { int cas; char source[2050][50]; char tarjan[3000]; scanf("%d",&cas); int ca=1; int nn,mm; while(cas--) { cin>>nn>>mm; for(int i=0;i<nn;i++) { cin>>source[i]; } int sum; cout<<"Case #"<<ca++<<":"<<endl; for(int i=0;i<mm;i++) { int ans=0; cin>>tarjan>>sum; for(int j=0;j<nn;j++) { int tmp=dist(source[j],tarjan); if(tmp<=sum) { ans++; } } cout<<ans<<endl; } } return 0; }