编辑距离：文本相似度算法

概念解释： 
编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同，所以一般会用来表示两个字符串的相似度。允许的操作包括修改一个字符，插入一个字符，删除一个字符。应用范围非常广泛，例如抄袭检测，NLP。 
要想知道从一个字符串转成另一个字符串的最少变换次数，我们就需要用一个算法，来求出两个字符串之间的最小编辑距离，最经典的算法，就是动态规划。

算法思路： 
动态规划算法，如果一直死抠细节是永远找不到状态和转移方程的，还是要更加注重状态的转移。在这个问题里面，字符串变换的方法有修改、删除、插入三种，那么我们的转移方程应该也包含三个部分，首先是状态，定义如下： 
两个字符串A，B，长度分别为n，m，状态dp[i][j]表示A字符串0 ~ i 子串与B字符串0 ~ j 子串之间的编辑距离，那么可以得到状态转移方程： 
**插入：**dp[i][j] = dp[i][j-1] + 1 
**删除：**dp[i][j] = dp[i-1][j] + 1 
**修改：**dp[i][j] = dp[i][j-1] + !(A[i]==B[j]) 
三者的最小值，就是状态dp[i][j]的解 
之后是初始状态，很明显，dp[0][0]=0，dp[i][0]=i，dp[0][j]=j 。

代码：

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int len1, len2, dp[1005][1005];char st1[1005], st2[1005];int main(){    while(~scanf("%d %s %d %s",&len1,st1,&len2,st2))    {        memset(dp,0,sizeof(dp));        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++)            {                dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1), dp[i-1][j-1]+(st1[i-1]!=st2[j-1]));            }        }        printf("%d\n",dp[len1][len2]);    }    return 0;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

总结： 
虽然思路挺简单，代码也不长，编辑距离的概念也是在实际中应用广泛的一个东西，也让我再次体会到动规的神奇。