编辑距离
问题描述
当一个智能终端将一行正文更新，并用新的目标串y[1..n]来替换现存的源串X [l..m]时，可有几种方式来做这种变换：源串中的单个字符可被删除(delete)；被替换 (replace)；或被复制到目标串中去(copy)；字符也可被插入(insert)；源串中的两个相邻字符可进行交换并复制到目标串中去(twiddle)；在完成其它所有操作之后，源串中余下的全部后缀就可用删至行末的操作删除(kill)。
例如，将源"algorithm"转换成目标串"altruistic"的一种方法是采取下面的操作序列:
操作 目标串 源串 copy a a lgorithm copy l al gorithm replace g by t alt orithm delete o alt rithm copy r altr ithm insert u altru ithm insert i altrui ithm insert s altruis ithm twiddle it into ti altruiti hm insert c altruitic hm kill hm altruitic
要达到这个结果还可有其它一些操作序列。操作delete,replace，copy，insert，twiddle和kill中每一个都有一个相联系的代价cost。例如
cost(delete)=3;
cost(replace)=6;
cost(copy)=5;
cost(insert)=4;
cost(twiddle)=4;
cost(kill)=被删除的串长*cose(delete)-1;
一个给定的操作序列的代价为序列中各操作代价之和。例如上述操作序列的代价为
3*cost(copy)+cost(replace)+cost(delete)+3*cost(insert)+cost(twiddle)+cost(kill)
=3*5+6+3+3*4+4+2*3-1
=45
给定两个序列x[1..m],y[1..n]和一些操作代价集合，X到Y的编辑距离为将X转化为Y的最"便宜"的转换序列的代价。请给出一个算法来找出x[1..m]至y[1..n]的编辑距离，并输出一个最优转换序列。