【Python】接頭辞・接尾辞・部分文字列のすべてに該当する最長のサブ文字列を検索する方法

与えられた文字列の中から、「接頭辞（プレフィックス）」かつ「接尾辞（サフィックス）」であり、さらに文字列の途中にも部分文字列として現れる最長のサブ文字列を見つける問題を考えてみましょう。該当するサブ文字列が存在しない場合は -1 を返します。

例えば、入力が "languagepythonlanguageinterestinglanguage" の場合、先頭・末尾・そして文字列の途中にも現れる "language" が答えとなります。

解決のアプローチ：LPS配列を活用する

この問題は、KMP法（Knuth–Morris–Pratt法）でも使われる「LPS配列」（各位置における「最長の接頭辞かつ接尾辞」の長さを記録した配列）を利用すると、線形時間で効率的に解くことができます。

ステップ1：get_lps() 関数の定義

1. 引数として文字列を受け取ります。
2. n に文字列の長さを代入します。
3. サイズ n の配列 long_pref_suff を作成し、すべて 0 で初期化します。
4. size = 0、long_pref_suff[0] = 0、i = 1 とします。
5. i < n の間、以下を繰り返します。
   • string[i] と string[size] が一致する場合：size を 1 増やし、long_pref_suff[i] = size として i を進めます。
   • 一致しない場合：size が 0 でなければ size = long_pref_suff[size - 1] とし、0 なら long_pref_suff[i] = 0 として i を進めます。
6. 完成した long_pref_suff を返します。

ステップ2：メイン処理での判定

1. get_lps() を呼び出して LPS 配列を取得します。
2. 末尾の値 long_pref_suff[n - 1] が 0 なら、候補が存在しないため -1 を返します。
3. 文字列の途中（インデックス 0 ～ n-2）に long_pref_suff[n - 1] と同じ値が現れれば、その長さの接頭辞が途中にも含まれていることが確定するため、string[0:long_pref_suff[i]] を返します。
4. 途中に現れない場合は、より短い候補 long_pref_suff[long_pref_suff[n - 1] - 1] を調べます。これが 0 なら -1、そうでなければその長さ分の接頭辞を返します。

実装例

以下のコードで実際の動作を確認してみましょう。

def get_lps(string):
    n = len(string)
    long_pref_suff = [0] * n
    size = 0
    i = 1
    while i < n:
        if string[i] == string[size]:
            size += 1
            long_pref_suff[i] = size
            i += 1
        else:
            if size != 0:
                size = long_pref_suff[size - 1]
            else:
                long_pref_suff[i] = 0
                i += 1
    return long_pref_suff

def get_longest_substr(string):
    long_pref_suff = get_lps(string)
    n = len(string)
    if long_pref_suff[n - 1] == 0:
        return -1
    for i in range(n - 1):
        if long_pref_suff[i] == long_pref_suff[n - 1]:
            return string[0:long_pref_suff[i]]
    if long_pref_suff[long_pref_suff[n - 1] - 1] == 0:
        return -1
    return string[0:long_pref_suff[long_pref_suff[n - 1] - 1]]

string = "languagepythonlanguageinterestinglanguage"
print(get_longest_substr(string))

実行結果

入力：

"languagepythonlanguageinterestinglanguage"

出力：

language

計算量について

LPS 配列の構築は文字列の長さ n に対して O(n)、その後の走査も O(n) であるため、全体の計算量は O(n)、必要な追加メモリも O(n) に収まります。すべての接頭辞と接尾辞を総当たりで比較する単純な方法では O(n²) 以上の時間がかかるため、長い文字列を扱う場面ではこの手法が特に有効です。