编辑距离
   

　　当一个智能终端将一行正文进行更新，并用目标串Ｙ（１....Ｎ）耒替换现存原串Ｘ(１....Ｍ)时，可以有如下几种方式做这种变换：

　　(1)源串的单个字符可被删除、替换或被复制到目标串中去；
　　(2)字符可以被插入；
　　(3)源串中两个相邻的字符可以进行交换并复制到目标串中去；
　　(4)在完成所有操作变换后，源串中余下的全部后缀用删至行末的操作删除。

　　例如：将源串：algorithm转换成目标串altruistic的一种方法是采用下面的操作序列：

　　

　　编程完成任务：

　　要达到这个结果还可以有其它的一些操作序列。每个操作都有一定的代价，一个给定序列的操作代价是序列中处各操作代价之和，所谓编辑距离是指将源串转换为目标串时应有最小的序列操作代价，操作代价和串由ＣＥ３１．ＴＸＴ给出，文件第一行为各操作代价，依次为:copy replace delete inscrt twiddlc kill，第二行是目标串，第三行是源串，串长不大于300 ，输出格式参考上表，最后列出操作序列代价表达之和


    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有