題意：編輯距離，求滿足步數小於d的個數。
[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 2000000000
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
int dp[20][20];
int n , m ;
char a[1500][20] ;
char b[20] ;
int main()
{
#ifndef ONLINE_JUDGE
freopen("acm.txt", "r", stdin);
#endif
int t ;
cin >> t ;
int ca = 0 ;
while( t -- )
{
cin >> n >> m ;
for (int i = 0 ;i < n ;i ++ )cin >> a[i] ;
printf("Case #%d:\n",++ca) ;
for (int i = 0 ;i < m ;i ++ )
{
cin >> b ;
int d ;
cin >> d ;
int ans = 0 ;
int l2 = strlen(b) ;
for (int j = 0 ;j < n ;j ++ )
{
int l1 = strlen(a[j]) ;
if(abs(l1 - l2 ) > d )continue ;
for (int k = 0 ;k <= l1 ;k ++ )
dp[k][0] = k ;
for (int k = 0 ;k <= l2 ;k ++ )
dp[0][k] = k ;
for (int k = 1 ;k <= l1 ;k ++ )
{
for (int k1 = 1 ;k1 <= l2 ;k1 ++ )
{
if(b[k1 - 1] == a[j][k - 1])dp[k][k1] = dp[k - 1][k1 - 1] ;
else{
dp[k][k1] = min(dp[k - 1][k1 - 1] + 1 ,min(dp[k - 1][k1] + 1 ,dp[k][k1 - 1] + 1 )) ;
}
}
}
if(dp[l1][l2] <= d)ans ++ ;
}
cout << ans << endl;
}
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 2000000000
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
int dp[20][20];
int n , m ;
char a[1500][20] ;
char b[20] ;
int main()
{
#ifndef ONLINE_JUDGE
freopen("acm.txt", "r", stdin);
#endif
int t ;
cin >> t ;
int ca = 0 ;
while( t -- )
{
cin >> n >> m ;
for (int i = 0 ;i < n ;i ++ )cin >> a[i] ;
printf("Case #%d:\n",++ca) ;
for (int i = 0 ;i < m ;i ++ )
{
cin >> b ;
int d ;
cin >> d ;
int ans = 0 ;
int l2 = strlen(b) ;
for (int j = 0 ;j < n ;j ++ )
{
int l1 = strlen(a[j]) ;
if(abs(l1 - l2 ) > d )continue ;
for (int k = 0 ;k <= l1 ;k ++ )
dp[k][0] = k ;
for (int k = 0 ;k <= l2 ;k ++ )
dp[0][k] = k ;
for (int k = 1 ;k <= l1 ;k ++ )
{
for (int k1 = 1 ;k1 <= l2 ;k1 ++ )
{
if(b[k1 - 1] == a[j][k - 1])dp[k][k1] = dp[k - 1][k1 - 1] ;
else{
dp[k][k1] = min(dp[k - 1][k1 - 1] + 1 ,min(dp[k - 1][k1] + 1 ,dp[k][k1 - 1] + 1 )) ;
}
}
}
if(dp[l1][l2] <= d)ans ++ ;
}
cout << ans << endl;
}
}
return 0;
}
