Pythonで2つの文字列の共通プレフィックス（接頭辞）を抽出して圧縮するプログラム

問題の概要

2つの文字列 s と t（いずれも小文字の英字で構成）が与えられたとします。このとき、3つのペアからなるリストを作成します。各ペアは (l, k) の形式で表され、k は文字列、l はその長さです。

3つのペアの中身は次のとおりです。

• 1つ目：s と t の最長共通プレフィックス（共通接頭辞）p
• 2つ目：p を取り除いた後の s の残りの部分 s'
• 3つ目：p を取り除いた後の t の残りの部分 t'

最終的な出力は、[(pの長さ, p), (s'の長さ, s'), (t'の長さ, t')] という形式になります。

たとえば、入力が s = "science"、t = "school" の場合、先頭の "sc" が共通しているため、出力は次のようになります。

[(2, 'sc'), (5, 'ience'), (4, 'hool')]

解決の手順

この問題は、次の手順で解くことができます。

• 空文字列 lcp を用意する
• i を 0 から min(len(s), len(t)) - 1 まで繰り返す
  • s[i] と t[i] が一致していれば、lcp に s[i] を追加する
  • 不一致になった時点で break すると、より安全に共通プレフィックスを求められる
• s_rem := s の len(lcp) 番目以降の部分文字列
• t_rem := t の len(lcp) 番目以降の部分文字列
• [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)] を返す

実装例

以下にPythonでの実装例を示します。なお、元のアルゴリズムでは不一致が起きてもループが継続するため、途中で異なる文字が現れた後に再び一致した場合に誤った結果になる可能性があります。ここでは break を加えて、より堅牢な形にしています。

def solve(s, t):
    lcp = ''
    for i in range(min(len(s), len(t))):
        if s[i] == t[i]:
            lcp += s[i]
        else:
            break  # 不一致の時点で共通プレフィックスは終了

    s_rem = s[len(lcp):]
    t_rem = t[len(lcp):]
    return [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)]

s = "science"
t = "school"
print(solve(s, t))

入力

"science", "school"

出力

[(2, 'sc'), (5, 'ience'), (4, 'hool')]

計算量について

このアルゴリズムは、短い方の文字列の長さを n としたとき、時間計算量 O(n)、空間計算量 O(n) で動作します。文字列スライスによって残りの部分を簡単に取得できるため、非常にシンプルかつ効率的な実装となっています。