以HDU 4323为例

首先介绍一下什么叫做Levenshtein distance

编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字>符替换成另一个字符，插入一个字符，删除一个字符。
sitten （k→s）

sittin （e→i）

sitting （→g）

俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

from Wikipedia

动态规划是解决此类问题的常用方法，用二维数组dpi表示源字符串前 i 位变成目标串前 j 位的编辑距离，

dp[i][j] = min( dp[i-1][j]+1 , dp[i][j-1]+1 , dp[i-1][j-1]+!(str1[i]==str2[j]) )

以”sailn”和”failing”这两个字符串作例子,字符串从1开始计数

用矩阵表示为

#	0	f	a	i	l	i	n	g
0
s
a
i
l
n

则初始化后为

#	0	f	a	i	l	i	n	g
0	0	1	2	3	4	5	6	7
s	1
a	2
i	3
l	4
n	5

初始化后，dpi,dp0都已被赋值，现在计算dp1，

dp[0][1]+1=2;dp[1][0]+1=2;dp[0][0]+!(str1[1]==str2[2])=1;

则dp1=1

以此类推，得到最终矩阵

#	0	f	a	i	l	i	n	g
0	0	1	2	3	4	5	6	7
s	1	1	2	3	4	5	6	7
a	2	2	1	2	3	4	5	6
i	3	3	2	1	2	3	4	5
l	4	4	3	2	1	2	3	4
n	5	5	4	3	2	2	2	3

两字符串的编辑距离就为矩阵最右下角的值

但是在此题中如果计算每对字符串的编辑距离会超时，需要进行一点小优化

题目中给出了两字符串需要满足的最大编辑距离，那么可在计算两字符串编辑距离之前先判断两字符串长度之差，若之差已大于最大距离，那么必然不符合题意，优化后，960ms险过，汗！

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define calLD calLevenshteindistance
using namespace std;
int dp[11][11]={0};
string dict[1501];
 
int min(int a,int b,int c)
{
    int t=(a<b?a:b);
    return (t<c?t:c);
}
int calLD(string s1,string s2,int dis)
{
    memset(dp,0,sizeof(dp));
    int len1=s1.size();
    int len2=s2.size();
    if(len1-len2 <(0-dis) || len1-len2>dis) return 0;
    s1='#'+s1;
    s2='#'+s2;
    int cnt=0;
    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++)
        {
            int flag=(s1[i]!=s2[j]);
            dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+flag);
        }
    }
    return (dp[len1][len2]<=dis);
 
}
int main()
{
//    int res=calLD("kitten","sitting");
//    cout<<res<<endl;
    int t,cas=1;
    cin>>t;
    while(cas<=t)
    {
        //memset(dict,0,sizeof(dict));
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            cin>>dict[i];
        }
        cout<<"Case #"<<cas++<<":\n";
        string toquery="";
        int dis,ans=0;
        for(int i=0;i<m;i++)
        {
            ans=0;
            cin>>toquery>>dis;
            for(int j=0;j<n;j++)
            {
                if(calLD ( toquery,dict[j],dis ))
                     ans++;
            }
            cout<<ans<<endl;
        }
 
    }
    return 0;
}