您所在位置：主题：请教一个字符串匹配的算法（常用）
Garand
[专家分：340] 发布于 2007-11-23 22:12:00
老师给出了道题，编写类似于linux下的diff这样问件比较程序，我看了一下需要用到如下这个动态规划的算法，好像在搜索中比较常用：http://www.avatar.se/molbioinfo2001/dynprog/dynamic.html
这个算法求出从一个字符串变换到另一个字符串至少需要多少次添加，删除，或插入操作，以及在什么地方进行这些操作。这个算法基本上能够看懂，只是有一个地方不明白，
Mi,j-1 + w (gap in sequence #1),
Mi-1,j + w (gap in sequence #2)]
算法讲解中出现上面两句，请问这个gap是指各字符串中含有的空格数目吧？可是文中开头就说Since this example assumes there is no gap opening or gap extension penalty, the first row and first column of the matrix can be initially filled with 0. 也就是说矩阵第一行和第一列为0是因为假定各字符串都不包含空格，也就是 w = 0，可是如果实际应用过程中字符串包含空格该怎么办呢？请高手讲解一下，不胜感激
这个算法求出从一个字符串变换到另一个字符串至少需要多少次添加，删除，或插入操作，以及在什么地方进行这些操作。这个算法基本上能够看懂，只是有一个地方不明白，
Mi,j-1 + w (gap in sequence #1),
Mi-1,j + w (gap in sequence #2)]
算法讲解中出现上面两句，请问这个gap是指各字符串中含有的空格数目吧？可是文中开头就说Since this example assumes there is no gap opening or gap extension penalty, the first row and first column of the matrix can be initially filled with 0. 也就是说矩阵第一行和第一列为0是因为假定各字符串都不包含空格，也就是 w = 0，可是如果实际应用过程中字符串包含空格该怎么办呢？请高手讲解一下，不胜感激