Pythonで部分列として指定文字列を含む最小の部分文字列を求める方法

問題の概要

2つの文字列 s と t が与えられたとき、s の中から「t が部分列（subsequence）として含まれる」最短の部分文字列を見つけることを考えます。該当する部分文字列が存在しない場合は空文字列を返し、最短の候補が複数ある場合は最も左側にあるものを採用します。

例えば、入力が s = "abcbfbghfb"、t = "fg" の場合、出力は fbg となります。

解法のアルゴリズム

この問題は動的計画法（DP）を用いて効率的に解くことができます。手順は以下の通りです。

• N := 文字列 S の長さとする
• dp := 長さ N のリストを作成し、すべて無限大（INF）で初期化する
• i を 0 から N-1 まで繰り返す：
  • S[i] が T[0] と一致する場合、dp[i] := 1 とする
• j を 1 から T の長さ-1 まで繰り返す：
  • last := 新しいマップ（辞書）を作成する
  • dp2 := 長さ N のリストを作成し、すべて INF で初期化する
  • i を 0 から N-1 まで繰り返す：
    • S[i] が T[j] と一致する場合：
      • prev_i := last から T[j-1] に対応する値を取得する
      • prev_i が None でない場合、dp2[i] := dp[prev_i] + (i - prev_i) とする
    • last[S[i]] := i とする
  • dp := dp2 と更新する
• m := dp の最小値
• i := dp において m が格納されているインデックス
• m が INF の場合は空文字列を返す
• それ以外の場合、S[i - dp[i] + 1 : i] の範囲の部分文字列を返す

実装例

以下にPythonでの実装例を示します。

class Solution:
   def solve(self, S, T):
      INF = float("inf")
      N = len(S)
      dp = [INF] * N
      for i in range(N):
         if S[i] == T[0]:
            dp[i] = 1
      for j in range(1, len(T)):
         last = {}
         dp2 = [INF] * N
         for i in range(N):
            if S[i] == T[j]:
               prev_i = last.get(T[j − 1], None)
               if prev_i is not None:
                  dp2[i] = dp[prev_i] + (i − prev_i)
            last[S[i]] = i
         dp = dp2
      m = min(dp)
      i = dp.index(m)
      if m == INF:
         return ""
      return S[i − dp[i] + 1 : i + 1]
ob = Solution()
print(ob.solve("abcbfbghfb","fg"))

入力

"abcbfbghfb","fg"

出力

fbg

コードのポイント

このアルゴリズムでは、各文字について「直前の文字がどこに出現したか」を辞書 last で管理することで、t の各文字を順番にたどる最短経路を効率的に計算しています。計算量は O(N × |T|) となり、単純な全探索よりも高速に動作します。また、dp 配列には「その位置で終わる有効な部分文字列の長さ」が記録されるため、最終的に最小値の位置から部分文字列を切り出すだけで答えが得られます。