字符串编辑距离（Levenshtein距离）算法

• 介绍：
  Levenshtein距离是一种计算两个字符串间的差异程度的字符串度量（string metric）。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时，其中编辑单个字符（比如修改、插入、删除）所需要的最少次数。
• 例子：
  从字符串“kitten”修改为字符串“sitting”只需3次单字符编辑操作，如下：
  sitten ( k -> s )
  sittin ( e -> i )
  sitting ( _ -> g )
  因此“kitten”和“sitting”的Levenshtein距离为3。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int lena, lenb;
char a[10010], b[10010];
int dp[10010];
void work() {
    for(int j=1; j<=lenb; j++) dp[j] = j;
    int t1, t2;
    for(int i=1; i<=lena; i++) {
        t1 = dp[0]++;
        for(int j=1; j<=lenb; j++) {
            t2 = dp[j];
            if(a[i-1]==b[j-1])
                dp[j] = t1;
            else
                dp[j] = min(t1, min(dp[j-1], dp[j]))+1;
            t1 = t2;
        }
    }
    printf("%d\n", dp[lenb]);
}
int main() {
    scanf("%s%s", a, b);
    lena = strlen(a);
    lenb = strlen(b);
    work();
    return 0;
}