Pythonで2つの文字列を含む最短スーパーシーケンス（共通超系列）の長さを求めるプログラム

2つの文字列 s と t が与えられたとき、s と t の両方を部分列として含む最短の文字列（最短共通スーパーシーケンス）の長さを求める問題を考えてみましょう。

例えば、入力が s = "pipe"、t = "people" の場合、答えは 7 になります。これは「pieople」という文字列が、両方の文字列を部分列として含む最短の例の一つだからです。

解法の考え方：LCS（最長共通部分列）を利用する

この問題は動的計画法（DP）を使って効率的に解けます。ポイントとなるのは次の関係式です。

最短スーパーシーケンスの長さ = len(s) + len(t) − LCS(s, t)

つまり、まず2つの文字列の最長共通部分列（LCS）の長さを求めておけば、共通する部分を1回だけ使うことで、全体の長さからその分を差し引いたものが答えになります。

アルゴリズムの手順

• m を s の長さ、n を t の長さとします。
• (m + 1) × (n + 1) のサイズの2次元表 table を用意し、すべて 0 で初期化します。
• i を 0 から m まで、j を 0 から n まで順に走査します。
  • i が 0 または j が 0 の場合は table[i][j] = 0 とします（どちらかの文字列が空の場合、LCSは0）。
  • s[i - 1] と t[j - 1] が一致する場合は、table[i][j] = 1 + table[i - 1][j - 1] とします（共通の文字を見つけたのでLCSが1増える）。
  • それ以外の場合は、table[i][j] = max(table[i][j - 1], table[i - 1][j]) とします（片方の文字列の末尾を無視した場合の最大値を採用）。
• 最後に m + n − table[m][n] を返します。これが最短スーパーシーケンスの長さです。

Pythonでの実装例

以下に実際のコードを示します。

class Solution:
    def solve(self, s, t):
        m = len(s)
        n = len(t)
        # (m+1) x (n+1) のDPテーブルを0で初期化
        table = [[0 for i in range(n + 1)] for j in range(m + 1)]
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0:
                    table[i][j] = 0
                else:
                    if s[i - 1] == t[j - 1]:
                        # 文字が一致：LCSが1つ伸びる
                        table[i][j] = 1 + table[i - 1][j - 1]
                    else:
                        # 一致しない場合：より大きい方を採用
                        table[i][j] = max(table[i][j - 1], table[i - 1][j])
        return m + n - table[m][n]

ob = Solution()
s = "pipe"
t = "people"
print(ob.solve(s, t))

入力

"pipe", "people"

出力

7

計算量について

このアルゴリズムの時間計算量は O(m × n)、空間計算量も O(m × n) です。2つの文字列の長さの積に比例するため、比較的短い文字列に対しては十分高速に動作します。