C++での最短の一般的なスーパーシーケンス

2つの文字列str1とstr2があるとすると、サブシーケンスとしてstr1とstr2の両方を持つ最短の文字列を見つける必要があります。結果は複数ある可能性があるため、そのうちの1つのみを返します。

ご存知のように、文字列Sは、Tからいくつかの文字を削除すると（おそらく0で、文字はTから任意の場所で選択されます）、文字列Sになる場合は文字列Tのサブシーケンスと呼ばれます。

したがって、入力が「acab」、「bac」のような場合、出力は「bacab」になります。これは、指定された2つの文字列がこれのサブシーケンスであるためです。

これを解決するには、次の手順に従います-

• 関数getLCS（）を定義します。これには、s1、s2、

  が必要です。

• ret：=空の文字列

• n：=s1のサイズ、m：=s2のサイズ

• サイズ（n + 1）x（m + 1）の2D配列dpを1つ定義します

• i：=n、j：=m

• s1：=s1の前に空白の文字列を連結する

• s2：=s2の前に空白の文字列を連結する

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

  • 初期化j：=1の場合、j <=mの場合、更新（jを1増やします）、実行-

    • s1[i]がs2[j]と同じ場合、-

      • dp [i、j]：=1 + dp [i-1、j-1]

    • それ以外の場合

      • dp [i、j]：=dp [i-1、j]およびdp [i、j-1]の最大値

• （iはゼロ以外、jはゼロ以外）、do-

  • dp [i、j]がdp [i-1、j]と同じ場合、-

    • （iを1減らします）

    • 次の部分を無視し、次の反復にスキップします

  • dp [i、j]がdp [i、j-1]と同じ場合、-

    • （jを1つ減らします）

    • 次の部分を無視し、次の反復にスキップします

  • ret：=ret + s1 [i]

  • （iを1減らします）

  • （jを1つ減らします）

• 配列を逆にするret

• retを返す

• メインの方法から、次のようにします-

• s3：=getLCS（str1、str2）

• ret：=空の文字列、i：=0、j：=0、k：=0

• k

  • i

    • ret：=ret + str1 [i]

    • （iを1増やします）

    • 次の部分を無視し、次の反復にスキップします

  • j

    • ret：=ret + str2 [j]

    • （jを1増やします）

    • 次の部分を無視し、次の反復にスキップします

  • ret：=ret + s3 [k]

  • （i、j、kを1つ増やします）

• i

  • ret：=ret + str1 [i]

  • （iを1増やします）

• j

  • ret：=ret + str2 [j]

  • （jを1増やします）

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string shortestCommonSupersequence(string str1, string str2){
      string s3 = getLCS(str1, str2);
      string ret = "";
      int i = 0;
      int j = 0;
      int k = 0;
      while (k < s3.size()) {
         if (i < str1.size() && str1[i] != s3[k]) {
            ret += str1[i];
            i++;
            continue;
         }
         if (j < str2.size() && str2[j] != s3[k]) {
            ret += str2[j];
            j++;
            continue;
         }
         ret += s3[k];
         k++;
         i++;
         j++;
      }
      while (i < str1.size()) {
         ret += str1[i];
         i++;
      }
      while (j < str2.size()) {
         ret += str2[j];
         j++;
      }
      return ret;
   }
   string getLCS(string s1, string s2){
      string ret = "";
      int n = s1.size();
      int m = s2.size();
      vector<vector<int> > dp(n + 1, vector<int>(m + 1));
      int i = n;
      int j = m;
      s1 = " " + s1;
      s2 = " " + s2;
      for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= m; j++) {
            if (s1[i] == s2[j]) {
               dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
               dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
         }
      }
      while (i && j) {
         if (dp[i][j] == dp[i - 1][j]) {
            i--;
            continue;
         }
         if (dp[i][j] == dp[i][j - 1]) {
            j--;
            continue;
         }
         ret += s1[i];
         i--;
         j--;
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestCommonSupersequence("acab", "bac"));
}

入力

"acab", "bac"

出力

bacab