近似串匹配问题（动态规划）

1.问题描述

2.思路分析
两个字符串文本P和样本T，对齐方式不一样则差别数不一样，编辑距离是最小差别数。
根据上课讲的两个例子最长公共子序列和背包问题类比分析，这两个问题都是从最后开始分析的，最长公共子序列分为最后一位相同和最后一位不同的情况，背包问题分为不放最后一个物品和放最后一个物品的情况。
该题目可以分为最后一位相同和不相同的情况，样本P：p1 p2 … pi，文本T：t1 t2 … tj，最后一位的对齐方式有三种,
第一种：p1 p2 … pi pi不等于tj则有删除操作，差别数+1
t1 t2 … tj
第二种：p1 p2 … pi-1 pi 插入操作，差别数+1
t1 t2 … tj
第三种：p1 p2 … pi
t1 t2 … tj-1 tj 删除操作，差别数+1
设从pi到tj的最小差别数是num（i,j）
则有递推关系
pi=tj时，num(i,j)=min{ num(i-1,j-1), num(i-1,j)+1, num(i,j-1)+1}
pi≠tj时，num(i ,j)=min{ num(i-1,j-1)+1, num(i-1,j)+1, num(i,j-1)+1}
边界条件是，num(0,j)=j 执行j次删除
num(i,0)=i 执行i次插入

填充矩阵。
3.递推实现：

#include 
#include 
using namespace std;
//三个数取最小
int getMin(int a, int b, int c) {
	if (a < b && a < c)
		return a;
	if (b < a && b < c)
		return b;
	return c;
}
int main() {
	char p[12] = {'a', 'p', 'p', 'r', 'o', 'x', 'i', 'm', 'a', 't', 'l', 'y'};
	char t[12] = {'a', 'p', 'r', 'o', 'x', 'i', 'o', 'm', 'a', 'l', 'l', 'y'};
	int num[20][20] = {0};
	int m = sizeof(p);
	int n = sizeof(t);
	//根据边界值填充， num(i,0)=i num(0,j)=j
	for (int i = 1; i <= m; i++)
		num[i][0] = i;
	for (int j = 1; j <= n; j++)
		num[0][j] = j;
	//根据递推关系式
	for (int j = 1; j <= n; j++) {
		for (int i = 1; i <= m; i++) {
			if (p[i - 1] == t[j - 1]) { //如果最后一个字符相同
				num[i][j] = getMin(num[i - 1][j - 1], num[i - 1][j] + 1, num[i][j - 1] + 1);
			} else {
				num[i][j] = getMin(num[i - 1][j - 1] + 1, num[i - 1][j] + 1, num[i][j - 1] + 1);
			}
		}
	}
	//输出矩阵
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			cout << num[i][j] << "  ";
		}
		cout << endl;
	}
	cout << "两个字符串编辑距离是：" << num[m][n];
	return 0;
}

输出结果：

4

递归实现：

#include 
using namespace std;

//char p[5] = {'h', 'a', 'p', 'p', 'y'};
//char t[6] = {'h', 's', 'p', 'p', 'a', 'y'};
char p[12] = {'a', 'p', 'p', 'r', 'o', 'x', 'i', 'm', 'a', 't', 'l', 'y'};
char t[12] = {'a', 'p', 'r', 'o', 'x', 'i', 'o', 'm', 'a', 'l', 'l', 'y'};
int a[20][20] = {0};
int m = sizeof(p);
int n = sizeof(t);

//三个数取最小
int getMin(int a, int b, int c) {
	if (a < b && a < c)
		return a;
	if (b < a && b < c)
		return b;
	return c;
}
//给数组num[][]赋值
int getRes(int i, int j) {
	if (j == 0)
		return i;
	else if (i == 0)
		return j;
	else if (p[i - 1] == t[j - 1])
		return getMin(getRes(i - 1, j - 1), getRes(i - 1, j) + 1, getRes(i, j - 1) + 1);
	else
		return getMin(getRes(i - 1, j - 1) + 1, getRes(i - 1, j) + 1, getRes(i, j - 1) + 1);

}
int main() {
	cout << getRes(m, n);
}