Pythonで文字列の異なる部分文字列の個数を数える方法（トライ木による解法）

文字列 s が与えられたとき、その中に含まれる「空でない異なる部分文字列」が何種類あるかを求める問題を考えてみましょう。

例えば、入力が s = "abaa" の場合、出力は 8 になります。これは、部分文字列として ["a", "b", "ab", "ba", "aa", "aba", "baa", "abaa"] の8種類が存在するためです。

解法のアプローチ：トライ木（Trie）を使う

この問題は、トライ木と呼ばれるデータ構造を使うことで効率的に解くことができます。トライ木とは、文字列の集合を木構造で表現したもので、共通の接頭辞を持つ文字列同士が同じ経路を共有できるのが特徴です。これにより、重複する部分文字列を自動的にまとめて管理できます。

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

• まず、空のマップ（辞書）として trie を用意します。
• n を文字列 s の長さとします。
• i を 0 から n-1 まで繰り返します。
  • curr を trie に設定します。
  • j を i から n-1 まで繰り返します。
    • c に s[j] を代入します。
    • c が curr に存在しない場合、curr[c] に新しいマップを作成します。
    • curr を curr[c] に更新し、curr["*"] を True にして「ここで文字列が終わる」ことを記録します。

この操作により、すべての異なる部分文字列がトライ木に登録されます。あとは幅優先探索（BFS）でノードの総数を数えれば、それがそのまま異なる部分文字列の個数になります。

• キュー q を作成し、trie を挿入します。
• ans を 0 に初期化します。
• q が空になるまで以下を繰り返します。
  • ans に 1 を加算します。
  • t に q の先頭要素を取り出して代入します。
  • t 内の各キー c について、c が "*" でなければ t[c] をキューの末尾に追加します。
• 最後に ans - 1 を返します（ルートノード分を差し引くため）。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

from collections import deque

def solve(s):
    trie = {}
    n = len(s)
    for i in range(n):
        curr = trie
        for j in range(i, n):
            c = s[j]
            if c not in curr:
                curr[c] = {}
            curr = curr[c]
            curr["*"] = True

    q = deque([trie])
    ans = 0
    while q:
        ans += 1
        t = q.popleft()
        for c in t:
            if c != "*":
                q.append(t[c])
    return ans - 1

s = "abaa"
print(solve(s))

入力

"abaa"

出力

8

計算量について

このアルゴリズムでは、すべての開始位置と終了位置の組み合わせに対してトライ木を更新するため、時間計算量は O(n²) となり、最悪の場合の空間計算量も O(n²) になります。文字列の長さ n が非常に大きいケースでは、接尾辞配列や接尾辞オートマトンなど、より高度なデータ構造の活用を検討するとよいでしょう。