Pythonで文字列内の最長の反復部分文字列を見つける方法

Pythonでは、collectionsモジュールのdefaultdictを使うことで、入力文字列の各位置から始まるすべての部分文字列の出現回数を効率的に集計できます。

ポイントとなるのはgetsubsメソッドです。これはジェネレータ関数として実装されており、呼び出されるたびに指定位置から始まる部分文字列を、完全な文字列から1文字ずつ短くしたものまで順番にyield（生成）していきます。

コード例

from collections import defaultdict

def getsubs(loc, s):
    substr = s[loc:]
    i = -1
    while(substr):
        yield substr
        substr = s[loc:i]
        i -= 1

def longestRepetitiveSubstring(r):
    occ = defaultdict(int)
    # すべての部分文字列の出現回数を集計
    for i in range(len(r)):
        for sub in getsubs(i, r):
            occ[sub] += 1
    # 出現回数が2回未満の部分文字列を除外
    filtered = [k for k, v in occ.items() if v >= 2]
    if filtered:
        maxkey = max(filtered, key=len)  # 最も長い文字列を取得
        return maxkey
    else:
        raise ValueError("no repetitions of any substring of '%s' with 2 or more occurrences" % (r))

longestRepetitiveSubstring("hellopeople18654randomtexthellopeoplefromallaroundthe world")

処理の流れ

このプログラムは以下の手順で動作します。

• 集計フェーズ： 文字列の先頭から順に各位置を起点として、そこから始まるすべての部分文字列を生成し、defaultdict(int)で出現回数をカウントします。
• フィルタリング： 出現回数が2回以上の部分文字列だけをリストに残します。これにより、繰り返し登場する文字列のみが対象になります。
• 最長判定： max(filtered, key=len)によって、条件を満たす中で最も長い部分文字列を取得します。
• エラー処理： 繰り返しが一切存在しない場合は、ValueErrorを発生させて明確なメッセージを返します。

出力結果

上記のコードを実行すると、次のような出力が得られます。

'hellopeople'

この例では、入力文字列の中に「hellopeople」という部分が2回登場しているため、それが最長の反復部分文字列として検出されています。

注意点： このアプローチはシンプルで理解しやすい反面、すべての部分文字列を網羅的に調べるため、文字列が長くなると計算量がO(n²)以上に増大します。非常に長いテキストを扱う場合は、接尾辞配列（Suffix Array）や接尾辞木などのより高度なアルゴリズムを検討するとよいでしょう。