Pythonで文字列とその接尾辞の類似度の合計を求めるプログラム

問題の概要

文字列 input_str が与えられたとします。まず、この文字列からすべての接尾辞(サフィックス)を求めます。たとえば、文字列が「abcd」であれば、接尾辞は「abcd」「bcd」「cd」「d」の4つです。

次に、元の文字列と各接尾辞との「類似度」を、両者の最長共通接頭辞(先頭から何文字一致しているか)の長さとして定義します。そして、元の文字列とすべての接尾辞との類似度の合計を求めて返すのが、このプログラムの目的です。

入力例と計算過程

たとえば、入力が input_str = 'tpotp' の場合、出力は 7 になります。

文字列「tpotp」の接尾辞は、「tpotp」「potp」「otp」「tp」「p」の5つです。それぞれの接尾辞と元の文字列との類似度を確認すると、以下のようになります。

'tpotp' との類似度: 5(文字列全体が一致)
'potp'  との類似度: 0(先頭の p と t が不一致)
'otp'   との類似度: 0(先頭の o と t が不一致)
'tp'    との類似度: 2(tp まで一致)
'p'     との類似度: 0(先頭の p と t が不一致)

類似度の合計 = 5 + 0 + 0 + 2 + 0 = 7

解き方のアプローチ

各接尾辞について素朴に先頭から順番に比較していく方法でも解けますが、文字列が長くなると計算量が O(n²) に膨らんでしまいます。そこで、Z-algorithm(Z配列)の考え方を利用すると、線形時間 O(n) で効率よく求められます。

Z配列の各要素 Z[i] は、「文字列全体と、位置 i から始まる接尾辞との最長共通接頭辞の長さ」を表します。つまり、Z配列の総和がそのまま求めたい類似度の合計になります(先頭要素は文字列長 n そのものです)。

具体的な手順は以下の通りです。

• return_list(Z配列)を初期化し、最初の要素として文字列の長さを格納します。
• 変数 i(現在の位置)、p・q(前回見つけた一致区間の長さと開始位置)、r(現在の一致長)を用意します。
• i が文字列の長さに達するまで、以下を繰り返します。
  • 以前に見つかった一致区間(q < i < q+p)の中に i がある場合は、その情報を再利用します。return_list[i-q] の値が区間の残り幅以上なら再計算が必要になるため値をリセットし、そうでなければ既知の値をそのままコピーして比較を省略します。
  • 一致区間の外にある場合は、文字列の先頭から直接比較して一致長 r を求め、それを return_list に追加したうえで、区間情報(p, q)を更新します。
• ループを抜けたら、return_list の全要素の合計を返します。

実装例(Python)

以下が実際の実装例です。

def solve(input_str):
    # Z配列: 各位置での「先頭からの最長一致長」を格納
    return_list = [len(input_str)]
    i = 1          # 現在処理中の位置
    p, q = 0, 0    # 前回の一致区間(長さ p、開始位置 q)
    r = 0          # 現在の一致長

    while i < len(input_str):
        if q < i < (q + p):
            # 既存の一致区間内 → 情報を再利用
            if return_list[i - q] >= q + p - i:
                # 区間の端に達するため再計算が必要
                r = q + p - i
                p, q = 0, 0
            else:
                # 区間内の値をそのままコピー
                return_list.append(return_list[i - q])
                i += 1
                r = 0
                continue
        else:
            # 文字列の先頭から直接比較
            while i + r < len(input_str) and input_str[r] == input_str[i + r]:
                r += 1
            return_list.append(r)
            p, q = r, i
            i += 1
            r = 0

    return sum(return_list)


print(solve('tpotp'))

入力

'tpotp'

出力

7

まとめ

このプログラムでは、Z-algorithmの仕組みを応用することで、文字列とそのすべての接尾辞との類似度(最長共通接頭辞の長さ)の合計を、O(n) の線形時間で効率的に計算できます。素朴な全比較方式では O(n²) かかるところを、一度見つけた一致情報を再利用することで大幅に高速化できるのが最大のポイントです。