C++で最短スーパーストリング(最短共通超文字列)を求めるアルゴリズム

問題概要

文字列の配列 A が与えられたとき、A に含まれるすべての文字列を部分文字列として持つ、最も短い文字列(スーパーストリング)を1つ求めることを考えます。ただし、A 内のどの文字列も、他の文字列の部分文字列ではないものと仮定できます。

たとえば、入力が ["dbsh", "dsbbhs", "hdsb", "ssdb", "bshdbsd"] の場合、出力は "hdsbbhssdbshdbsd" となります。

この問題は、文字列同士の重なり(オーバーラップ)を辺のコストとみなすことで、巡回セールスマン問題(TSP)とよく似た構造になり、ビットDP(動的計画法)を用いて効率的に解くことができます。

アルゴリズムの考え方

ステップ1: calc() 関数の定義

まず、文字列 a の末尾に文字列 b を連結する際に新たに追加が必要となる文字数を計算する関数 calc(a, b) を定義します。

• 変数 i を 0 に初期化し、i が a のサイズ未満である間、以下を繰り返します。
  • a のインデックス i 以降の部分文字列が b の先頭と一致する場合、「b のサイズ − a のサイズ + i」を返します。
• どこでも一致しなかった場合は、b のサイズをそのまま返します。

この戻り値は「a の後ろに b をつなぐときに追加される文字数」を表しています。

ステップ2: メイン処理の流れ

1. 結果を格納する ret を空文字列で初期化し、n := A のサイズとします。
2. n × n の2次元配列 graph を定義し、graph[i][j] := calc(A[i], A[j])、graph[j][i] := calc(A[j], A[i]) を計算します。
3. サイズ 2^n × n の dp 配列と path 配列を用意します。dp[i][j] は「集合 i の文字列を使い、最後が j である場合の最短長」を表します。
4. minVal := 無限大、last := -1 で初期化します。
5. dp 配列の全要素を無限大(INT_MAX)で初期化します。
6. i を 0 から 2^n − 1 まで、j を 0 から n − 1 まで走査します。
   • i AND 2^j が非ゼロの場合、prev := i XOR 2^j とします(j を除いた部分集合)。
   • prev が 0 の場合、dp[i][j] := A[j] のサイズとします(最初の1文字列のみの場合)。
   • それ以外の場合、k を 0 から n − 1 まで走査し、「prev に k が含まれ、かつ dp[prev][k] が無限大ではなく、dp[prev][k] + graph[k][j] < dp[i][j]」を満たすなら、dp[i][j] := dp[prev][k] + graph[k][j]、path[i][j] := k と更新します。
7. i が 2^n − 1 に等しく、かつ dp[i][j] < minVal の場合、minVal := dp[i][j]、last := j と更新します。

ステップ3: 経路の復元と答えの構築

1. curr := 2^n − 1 とし、スタック st を用意します。
2. curr > 0 の間、last を st にプッシュし、temp := curr、curr := curr − 2^last、last := path[temp][last] と更新していきます。
3. st の先頭要素を取り出して i とし、ret := ret + A[i] とします。
4. st が空になるまで、j := st の先頭要素を取り出し、ret に A[j] の末尾 graph[i][j] 文字分を連結し、i := j とします。
5. ret を返します。

計算量は O(n² · 2ⁿ) となり、n が小さい範囲(目安として20程度まで)であれば現実的な時間で求解できます。

C++ 実装例

#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

まとめ

本記事では、文字列の配列からすべての要素を部分文字列として含む最短スーパーストリングを求める手法を紹介しました。ポイントは次の3点です。

• calc() 関数により、2つの文字列を連結する際の追加文字数(オーバーラップ量)を前計算する。
• ビットDPによって「使用済みの文字列集合 × 最後の文字列」を状態として最短長を求める。
• path 配列を辿ってスタックで経路を復元し、実際のスーパーストリングを構築する。

同じ文字列の並びに対して複数の最短解が存在しうるため、出力は入力の並び順や実装の詳細によって異なる場合がありますが、いずれも有効な最短スーパーストリングとなります。