C++で最短のスーパーストリングを見つける

文字列の配列Aがあるとすると、Aの各文字列をサブ文字列として含む最小の文字列を見つける必要があります。また、Aの文字列がAの別の文字列のサブ文字列ではないと想定することもできます。

したがって、入力が["dbsh"、 "dsbbhs"、 "hdsb"、 "ssdb"、 "bshdbsd"]の場合、出力は "hdsbbhssdbshdbsd"

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

• 関数calc（）を定義します。これには、a、b、

  が必要です。

• 初期化i：=0の場合、i

  • インデックスiからendまでのaの部分文字列がbの先頭にある場合、-

    • bの戻りサイズ-a+iのサイズ

• bの戻りサイズ

• 主な方法から、これらの手順を実行します

• ret：=空の文字列

• n：=Aのサイズ

• サイズnxn −

  の2D配列グラフを1つ定義します

  • 初期化j：=0の場合、j

    • グラフ[i、j]：=calc（A [i]、A [j]）

    • グラフ[j、i]：=calc（A [j]、A [i]）

• サイズの配列dpを定義します：2 ^ nxn。

• サイズの配列パスを定義します：2 ^ nxn。

• minVal：=inf

• 最後：=-1

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

  • 初期化j：=0の場合、j

    • dp [i、j]：=inf

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

  • 初期化j：=0の場合、j

    • i AND 2 ^ jがゼロ以外の場合、

      • 前：=i ^（2 ^ j）

    • prevが0と同じ場合、-

      • dp [i、j]：=A [j]

        のサイズ

    • それ以外の場合

      • 初期化k：=0の場合、k

        • prev AND 2 ^kおよびdf[prev、k]がinfおよびdf [prev、k] +graph [k、j]

          • dp [i、j]：=dp [prev、k] +グラフ[k、j]

          • path [i、j]：=k

  • iが2^n-1およびdp[i、j]

    • minVal：=dp [i、j]

    • 最後：=j

• curr：=2 ^ n-1

• 1つのスタックstを定義する

• curr> 0の場合、実行-

  • 最後をstに挿入

  • temp：=curr

  • curr：=curr-（2 ^ last）

  • last：=path [temp、last]

• i：=stの最上位要素

• stから要素を削除

• ret：=ret + A [i]

• （stが空ではない）間、-

  • j：=stの最上位要素

  • stから要素を削除

  • ret：=retは、A [j]の部分文字列を（A[j]のサイズ-graph[i、j]から終了まで）から連結します

  • i：=j

• retを返す

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int calc(string& a, string& b){
      for (int i = 0; i < a.size(); i++) {
         if (b.find(a.substr(i)) == 0) {
            return b.size() - a.size() + i;
         }
      }
      return (int)b.size();
   }
   string shortestSuperstring(vector<string>& A){
      string ret = "";
      int n = A.size();
      vector<vector<int> > graph(n, vector<int>(n));
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            graph[i][j] = calc(A[i], A[j]);
            graph[j][i] = calc(A[j], A[i]);
         }
      }
      int dp[1 << n][n];
      int path[1 << n][n];
      int minVal = INT_MAX;
      int last = -1;
      for (int i = 0; i < (1 << n); i++)
      for (int j = 0; j < n; j++)
      dp[i][j] = INT_MAX;
      for (int i = 1; i < (1 << n); i++) {
         for (int j = 0; j < n; j++) {
            if ((i & (1 << j))) {
               int prev = i ^ (1 << j);
               if (prev == 0) {
                  dp[i][j] = A[j].size();
               } else {
                  for (int k = 0; k < n; k++) {
                     if ((prev & (1 << k)) && dp[prev][k] !=
                     INT_MAX && dp[prev][k] + graph[k][j] < dp[i][j]) {
                        dp[i][j] = dp[prev][k] + graph[k][j];
                        path[i][j] = k;
                     }
                  }
               }
            }
            if (i == (1 << n) - 1 && dp[i][j] < minVal) {
               minVal = dp[i][j];
               last = j;
            }
         }
      }
      int curr = (1 << n) - 1;
      stack<int> st;
      while (curr > 0) {
         st.push(last);
         int temp = curr;
         curr -= (1 << last);
         last = path[temp][last];
      }
      int i = st.top();
      st.pop();
      ret += A[i];
      while (!st.empty()) {
         int j = st.top();
         st.pop();
         ret += (A[j].substr(A[j].size() - graph[i][j]));
         i = j;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"};
   cout << (ob.shortestSuperstring(v));
}

入力

{"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"}

出力

hdsbbhssdbshdbsd