Pythonで文字列内に2回以上出現する最長部分文字列の長さを求めるプログラム

小文字のみで構成された文字列 s が与えられたとき、s の中に少なくとも2回以上出現する最長の部分文字列の長さを求めます。そのような部分文字列が存在しない場合は 0 を返します。

たとえば、入力が s = "abdgoalputabdtypeabd" の場合、2回以上出現する最長の部分文字列は "abd" なので、出力は 3 になります。

解法のアプローチ：接尾辞（サフィックス）の活用

この問題は「接尾辞」という考え方を使うとスマートに解けます。文字列に2回以上現れる部分文字列は、必ず開始位置の異なる2つの接尾辞の共通接頭辞として現れます。そこで、すべての接尾辞を辞書順にソートすれば、似た接尾辞どうしが隣り合うため、隣接ペアの共通接頭辞だけを調べれば十分になります。

具体的な手順は次のとおりです。

• 関数 lcs(s1, s2) を定義します。2つの文字列の共通接頭辞を返します。
  • n := s1 と s2 の長さのうち小さい方
  • i を 0 から n-1 まで繰り返し、s1[i] と s2[i] が異なれば s1[:i] を返す
  • ループが完了したら s1[:n] を返す
• メインの solve 関数では以下を行います。
  • suffixes := 空のリストを作成
  • n := 文字列 s の長さ、max_len := 0
  • i を 0 から n-1 まで繰り返し、接尾辞 s[i:n] を suffixes に追加
  • suffixes をソートする
  • 隣接する2つの要素 a, b に対して rtr := lcs(a, b) を計算し、rtr の長さが max_len を超えれば更新
  • 最後に max_len を返す

実装例

それでは、実際のコードを見てみましょう。

def lcs(s1, s2):
    n = min(len(s1), len(s2))

    for i in range(n):
        if s1[i] != s2[i]:
            return s1[:i]
    return s1[:n]

def solve(s):
    suffixes = []
    n = len(s)
    max_len = 0

    for i in range(n):
        suffixes.append(s[i:n])

    suffixes.sort()

    for a, b in zip(suffixes, suffixes[1:]):
        rtr = lcs(a, b)

        if len(rtr) > max_len:
            max_len = len(rtr)

    return max_len

s = "abdgoalputabdtypeabd"
print(solve(s))

入力

"abdgoalputabdtypeabd"

出力

3

計算量のポイント

この方法では、接尾辞の生成に O(n²) の時間とメモリが必要で、ソートには O(n² log n) 程度かかります。短い文字列なら十分実用的ですが、より大きな入力に対応する場合は、接尾辞配列・接尾辞木や、二分探索＋ローリングハッシュを組み合わせた O(n log n) の高度な手法が知られています。まずはこのシンプルな実装で考え方を理解するのがおすすめです。