动态规划之寻找两个字符串最长公共子串

布满荆棘的人生 2022-07-28 01:43 155阅读 0赞

引入

寻找两个字符串的最长公共子串通常动态规划去解决。例如， 在单词“  raven” 和“  havoc” 中， 最长的公共子串是“  av”。 寻找最长公共子串常用于遗传学中，用于使用核苷酸中碱基的首字母对  DNA  分子进行描述。

思路  
    首先考虑暴力方式开始去解决这个问题。 给出两个字符串 A 和 B， 我们可以通过从 A 的第一个字符开始与 B 的对应的每一个字符进行比对的方式找到它们的最长公共子串。 如果此时  
没有找到匹配的字母， 则移动到 A 的第二个字符处， 然后从 B 的第一个字符处进行比对，以此类推。  
    而采用动态规划是更适合解决这个问题的方案。 这个算法使用一个二维数组存储两个字符串相同位置的字符比较结果。 初始化时， 该数组的每一个元素被设置为 0。 每次在这两个数组的  
相同位置发现了匹配， 就将数组对应行和列的元素加 1， 否则保持为 0。按照这种方式， 一个变量会持续记录下找到了多少个匹配项。 当算法执行完毕时， 这个变量会结合一个索引变量来获得最长公共子串  
设计函数  
function lcs(word1, word2) \{  
   var max = 0;  
   var index = 0;  
   var lcsarr = new Array(word1.length+1);  
   for (var i = 0; i <= word1.length+1; ++i) \{        //一次for循环构建二维数组，并全设置为0  
      lcsarr\[i\] = new Array(word2.length+1);        //注意二维数组的长度变化  
      for (var j = 0; j <= word2.length+1; ++j) \{  
         lcsarr\[i\]\[j\] = 0;  
      \}  
   \}  
   for (var i = 0; i <= word1.length; ++i) \{        //第二部分构建了用于保存字符匹配记录的表。  
      for (var j = 0; j <= word2.length; ++j) \{  
         if (i == 0 || j == 0) \{  
            lcsarr\[i\]\[j\] = 0;  
         \}  
         else \{  
            if (word1\[i-1\] == word2\[j-1\]) \{  
               lcsarr\[i\]\[j\] = lcsarr\[i-1\]\[j-1\] + 1;  
            \}  
            else \{  
               lcsarr\[i\]\[j\] = 0;  
            \}  
         \}  
         if (max < lcsarr\[i\]\[j\]) \{  
            max = lcsarr\[i\]\[j\];  
            index = i;  
         \}  
      \}  
   \}  
   var str = "";  
   if (max == 0) \{  
      return "";  
   \}  
   else \{  
      for (var i = index-max; i <= max; ++i) \{       //确认从哪里开始构建这个最长公共子串。 以变量  index  减去变量  max的差值作为起始点，  
         str += word2\[i\];                                        // 以变量  max  的值作为终点：  
      \}  
      return str;  
   \}     
\}  
       该函数的第一部分初始化了两个变量以及一个二维数组。 多数语言对二维数组的声明都很简单， 但在 JavaScript 中需要很费劲地在一个数组中定义另一个数组， 这样才能声明一个二维数组。第二部分构建了用于保存字符匹配记录的表。 数组的第一个元素总是被设置为 0。 如果两个字符串相应位置的字符进行了匹配， 当前数组元素的值将被设置为前一次循环中数组元素保存的值加 1。 比如， 如果两个字符串 "back" 和 "cace"， 当算法运行到第二个字符处时， 那么数值 1 将被保存到当前元素中， 因为前一个元素并不匹配， 0 被保存在那个元素中（ 0+1）。 接下来算法移动到下一个位置， 由于此时两个字符仍被匹配， 当前数组元素将被设置为 2（ 1+1）。 由于两个字符串的最后一个字符不匹配， 所以最长公共子串的长度是2。 最后， 如果变量 max 的值比现在存储在数组中的当前元素要小， max 的值将被赋值给这个元素， 变量 index 的值将被设置为 i 的当前值。 这两个变量将在函数的最后一部分用于确定从哪里开始获取最长公共子串。

测试

alert(lcs("ufrd","rfrg"));

数组  lcsarr  的状态展示了算法的执行过程：

显然函数执行后返回的结果是：fr