この記事は データ構造とアルゴリズム Advent Calendar 2020 21 日目の記事です.

20 日目の記事は @tugar さんの「モンテカルロ木探索についてのまとめ」でした.

22 日目の記事は @kampersanda さんの「ダブル配列のゲーム作った」です.

はじめに

この記事では擬接尾辞集合に対する接尾辞木の構築アルゴリズムを紹介し,その実装例を示します.

読者はトライ木基数木を知っていると仮定します.接尾辞木は記事内で簡単に説明しますがリンク先の Wikipedia の記事を読んで概念を知っておくと理解しやすいです.接尾辞木の構築アルゴリズムは記事内で紹介するので特に知っている必要はありません.

この記事で紹介するデータ構造が適用できる代表的な問題として次のものを考えます.記事の後半にて他の問題も紹介します.

問題 1. Parameterized String Matching Problem (Baker 1993)

文字と変数からなる文字列を parameterized string といいます.2つの parameterized string がマッチするとは,一方の文字列中の変数をもう一方の文字列中の変数に単射的に (違う変数は違う変数になるように) 置き換えたときに普通の文字列として等しいことをいいます.簡単のため小文字アルファベットで文字,大文字アルファベットで変数をあらわすことにすると,例えば s = "aXbY" と t = "aZbX" はマッチしますが s = "aXbX" と t = "aXbY" はマッチしません.

Parameterized string という概念は Baker (1993) によってプログラムのソースコードを検索する文脈で提案されました.プログラムのソースコードでは変数を一括でリネームしても意味が変わらないので,同じコード片を見つけたいときは通常の文字列マッチではなく parameterized string のマッチを考えたほうがよいだろう,というモチベーションだったようです.

Parameterized string matching は次の問題です:テキストと呼ばれる長い parameterized string と,複数のパターンと呼ばれる短い parameterized string が与えられます.テキストの部分 parameterized string であって各パターンにマッチする部分の個数を求めてください.

いつもどおり入出力仕様を書くと次のようになります.

入力

入力の 1 行目にはテキストをあらわす parameterized string,2 行目はパターンの個数をあらわす正整数, 3 + $i$ 行目には $i$ 番目のパターン $\mathit{pattern}_i$ をあらわす patarmeterized string が与えられます.入力のサイズは以下の条件を満たします.

ただし $| \cdots |$ は文字列の長さをあらわすものとします.

出力

各 $i$ に対して $i$ 番目のパターンにマッチするテキストの部分 parameterized string の個数を出力してください.異なる位置で出現する parameterized string は別のものと考えます.

入力例