编程之美3.3——计算字符串的相似度

问题：

1. 计算两个字符串的最长公共子序列(LCS)，且公共子序列在字符串中不需要是连续的。

2. 计算两个字符串的距离，完全相同的字符串距离为0，可以通过修改一个字符、增加一个字符或删除一个字符三种方式来使两个字符串相同，但这些方式会使得距离加1。

1.解法：

这两个问题的解法基本相同，都是二维的动态规划，都考虑字符串的后缀（实际上用动态规划更喜欢考虑前缀，但使用前缀时数组最好从位置1开始，因为dp数组的初始化一般要占用位置0，但字符串不方便从1开始读入，所以在解决问题是使用后缀，用位置n进行初始化）。

f(i,j)表示A从位置i开始的后缀与B从位置j开始的后缀的最长公共子序列Z从位置k开始的后缀的长度。这里的i,j都是阶段，也就是两个阶段变量，状态只有1个，决策有两个即相等或不等。

#include <iostream>#include <algorithm>#include <cstring>using namespace std;#define MAXN 10001char A[MAXN];char B[MAXN];int dp[MAXN][MAXN];// dp[i][j]表示字符串A从位置i开始的后缀与// 字符串B从位置j开始的后缀的距离int main(){scanf("%s", A);scanf("%s", B);int i, j, m, n;n = strlen(A);m = strlen(B);// 初始化,若一个序列为空,则字符串的距离为// 另一个字符串所取的后缀的长度for (j=m; j>=0; j--)dp[n][j] = m-j;for (i=n; i>=0; i--)dp[i][m] = n-i;for (i=n-1; i>=0; i--)for (j=m-1; j>=0; j--){if (A[i]==B[j])// 若相等，则字符串A的字符i与字符串B的字符j并没有增加距离，// 仍等于A从字符i+1开始的后缀与B从字符j+1开始的后缀的距离dp[i][j] = dp[i+1][j+1];else{// 若不相等,则A和B的距离加1，且取相应后缀组中三个距离中最小的那个dp[i][j] = dp[i+1][j+1]+1;dp[i][j] = min(dp[i][j], dp[i][j+1]+1);dp[i][j] = min(dp[i][j], dp[i+1][j]+1);}}for (i=0; i<=n; i++){for (j=0; j<=m; j++)printf("%d ", dp[i][j]);printf("\n");}printf("%d\n", dp[0][0]);}