编辑距离问题实验报告(共6页).doc

精选优质文档-倾情为你奉上算法设计与分析上 机 实 验 报 告专 业软件工程班 级软件1101学 号学生姓名付添完成日期2013-10-241. 上机题目及实验环境1.1上机题目：编辑距离问题1.2实验环境：CPU：intel内存：4G操作系统：windows xp软件平台：Microsoft Visual C+2. 算法设计与分析 对于本问题，大体思路为：把求解编辑距离分为字符串A从0个字符逐渐增加到全部字符分别想要变为字符串B该如何变化以及变化的最短距离。具体步骤如下:从文件中读出字符串存入str1 与str2中,d用来村每一步需要变化的次数。取str1，str2长度分别为n,m.分两种情况即A的长度为0而B不为0还有A不为0B为0，最后的编辑距离分别为m和n。一般情况，d矩阵为dnm，假定我们从d00开始一直进行以下操作到了dij的位置，如果A