最长公共子序列（三 | 存在多个解的情况）

2023-02-09 94

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 最长公共子序列（三 | 存在多个解的情况）

LCS_PLUS（存在多个解的情况）

💎关于LCS

前面我们已经详细进行讲述了关于LCS的问题，但有意思的是，前面我们都只是输出满足LCS的一个序列，但是现实问题总是复杂多变的，不可避免的的是两个字符串中的LCS很有可能不是唯一的，那么如果要求我们按字典序依次输出所有的LCS，我们又该怎么去做呢？不妨先思考一下，再往下看吧！

其实我们只需要回顾之前打表的时候，当b[i-1][j] 等于b[i][j-1]时便是有重复解的情况，此时长度表记录哪个都可以，但是回溯路径时两边便都要走。

代码如下

for (int i = 1; i <= len1; i++) {
    for (int j = 1; j <= len2; j++) {
      if (s1[i - 1] == s2[j - 1]) { //注：此处的s1与s2序列是从s1[0]与s2[0]开始的
        c[i][j] = c[i - 1][j - 1] + 1;
        b[i][j] = 1;//给每种情况打标记，后面方便输入路径
      }
      else { //c[i][j] = max(c[i][j-1], c[i-1][j])
        if (c[i][j - 1] > c[i - 1][j]) {
          c[i][j] = c[i][j - 1];
          b[i][j] = 2; //第二种情况
        }
        else  if (c[i][j - 1] < c[i - 1][j]) {
          c[i][j] = c[i - 1][j];
          b[i][j] = 3; //第三种情况
        }
        else if (c[i][j - 1] == c[i - 1][j]) {
          c[i][j] = c[i - 1][j];//第四种情况，回溯时两边都要走
          b[i][j] = 4;
        }
      }
    }
  }

整体看起来，虽然上面的打表结构并没有很大的变化，但是给方向数组b 赋了一个两边都回溯的情况（b[i][j]=4）却是很关键

void FindPath(int i, int j, string& text1, string& text2, string path) {
  if (i == 0 || j == 0) {
    reverse(path.begin(), path.end());
    ASN.insert(path);
    return;
  }//这里不同了，记得上面传参传长度哦
  if (b[i][j] == 1) {
    path += text1[i - 1];
    FindPath(i - 1, j - 1, text1, text2, path);
  }
  else if (b[i][j] == 2)
  {
    FindPath(i, j - 1, text1, text2, path);
  }
  else if (b[i][j] == 3)
  {
    FindPath(i - 1, j, text1, text2, path);
  }
  else if (b[i][j] == 4) {//两边都走
    FindPath(i - 1, j, text1, text2, path);
    FindPath(i, j - 1, text1, text2, path);
  }
}