编辑距离问题算法分析

本题提出了一些关于将字符串x[1..m]转换成y[1..n]的操作。这些操作有复制、替代、删除、插入、互换和终止。这些操作所需的开销是不同的，但每个操作的开销都可以看是一个我们已经的常量，我们假设复制和替代这类操作的开销要比插入和删除这类操作的开销少。我们用x[1..m]来保存原字符串，数组下标用i表示，初始化为1；用y[1..n]来保存转换后的字符串，数组下标用j来表示，初始化为1；数组z用来存放中间结果，下标用j来表示，初始化为0。