基础算法
假设我们有两个字符串：
，每个字符串由A C G T四个字母组成。
在两个字符串上，都有三种可能的编辑操作（突变）：
- 删除某个字符
- 在某个位置插入字符
- 改变某个字符
每一个编辑操作都有惩罚值。用D(R,B)表示字符串R和B的最小编辑距离(总惩罚值)。
在这里，我们将三种编辑操作的惩罚值都设为1。
定义矩阵D，X维和Y维分别表示字符串B和R。在矩阵的
上，我们尝试对两个字符串对应位置的字符进行匹配，并计算相应位置的分数。
在矩阵上DP的过程实际上具有生物学意义。比如，上下或者左右移动意味着插入或者删除，在对角线上移动意味着匹配/失配。
很明显，在对角线上移动比左右/上下移动更容易找到符合条件的匹配。
示例图片：
伪代码：
标签：字符,Vishkin,矩阵,Landau,编辑,字符串,移动 From： https://www.cnblogs.com/railgunRG/p/16731619.html