Pythonで文字列内の重複しない部分文字列の個数を求めるプログラム

問題の概要

ある文字列 s が与えられたとします。ここでの課題は、s から取り出せるすべての部分文字列のうち、重複しないもの(ユニークなもの)だけを抽出し、その総数を出力することです。

たとえば、入力が s = 'prrstvt' の場合、出力は 26 になります。

このとき得られる重複しない部分文字列は、以下の26種類です。

'pr'、'rrs'、'st'、'rr'、'tv'、'rstv'、'stvt'、'prrstv'、'prrstvt'、'rrstvt'、's'、'prrst'、'stv'、'rrstv'、'rst'、'v'、'tvt'、'rstvt'、'r'、'rs'、'vt'、't'、'prr'、'p'、'rrst'、'prrs'

解法の考え方

この問題は、「各位置で終わる部分文字列」を順番に生成していくことで効率的に解けます。具体的には、次の手順に従って処理を進めます。

• まず、結果を記録するための辞書 visited を新しく用意します。
• 文字列 s の各インデックス ind と、その位置にある文字 let について、以下の処理を繰り返します。
  • 新しい集合 temp を作成します。
  • visited に ind - 1 が存在する場合、直前の位置で終わるすべての部分文字列 has_let に対して、末尾に let を連結した文字列(has_let + let)を temp に追加します。
  • さらに、1文字のみの部分文字列として let そのものも temp に追加します。
  • temp を visited[ind] として保存します。
• すべての部分文字列を統合するための新しい集合 res を用意します。
• visited に格納された各集合の要素をすべて res に追加します。
• 最後に res のサイズ、つまり重複しない部分文字列の個数を返します。

集合(set)を利用することで、同一の部分文字列が自動的に除外されるため、重複チェックのロジックを明示的に書く必要がないのが大きなポイントです。

実装例

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

def solve(s):
   visited = dict()
   for ind, let in enumerate(s):
      temp = set()
      if ind-1 in visited:
         for has_let in visited[ind-1]:
            temp.add(has_let+let)
      temp.add(let)
      visited[ind] = temp
   res = set()
   for sets in visited:
      res.update(visited[sets])
   return len(res)

print(solve('prrstvt'))

入力

'prrstvt'

出力

26

計算量について

長さ n の文字列の場合、部分文字列は最大でも n(n+1)/2 個であり、それぞれの連結操作に最大で O(n) かかるため、全体の時間計算量・空間計算量は O(n³) 程度になります。短めの文字列であれば十分実用的ですが、非常に長い文字列を扱うケースでは、接尾辞配列や接尾辞木といったより高度なデータ構造の活用を検討するとよいでしょう。