問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
Aho–Corasick 法 (エイホーコラシック法) では PMA
(パターンマッチングオートマトン) と呼ばれるグラフを作り、PMA 上を移動することでパターンマッチングをおこないます。パターンマッチングをおこなう文字列 (テキスト) の長さを L とすると、必要な計算量は O(L) と極めて高速です。
この問題ではパターン (表れるかを判定したい文字列) が1つの場合の PMA
の構築を学びます。
最初にパターンを格納したトライ木を構築します。
例えば "abab" をパターンとした場合のトライ木は次の図のようになります。
トライ木の各頂点には「ある文字 ch を受け取ったときの遷移」 が定義されている場合があり、これを表しているのが図中の有向辺となります。ある頂点で文字 ch をラベルとして持つ出ていく辺があるなら、その頂点で文字 ch を受け取ったときにどの頂点に遷移するかが定義されています。文字 ch をラベルとして持つ出ていく辺がないならその頂点で文字 ch を受け取ったときの遷移は定義されてません。
ここで、根 (図の最も左にある、文字の書かれていない頂点) を始点として有向辺に沿ってある頂点 u に移動したとします。そして、通った経路のラベルを順に読んで得られる文字列を S とします。このとき、u を「S に対応する頂点、または単に頂点 S」と呼びます。各頂点に書かれている文字列が対応する文字列です。根は長さ 0 の文字列に対応します。また、根から u への経路で得られる文字列 S を「u に対応する文字列、または単に文字列 u」と呼びます。赤い頂点はパターンに対応する文字列であることを示しています。
次にこのトライ木に failure
と呼ばれる有向辺を追加することで PMA を構築することができます。
PMA の根以外の頂点は自身を始点とする failure
を必ず 1 つ持ちます。
長さ N の文字列の先頭 x (0 ≦ x ≦ N) 文字を削った文字列を接尾辞と言います。
例えば "abc" の接尾辞は "abc", "bc", "c", "" (長さ 0 の文字列) の 4 つです。
ある頂点 u から出る failure
は、「u が対応する文字列 S の、 S を除く接尾辞の中で、グラフ内に存在する最長の文字列 T の対応する頂点」へと引かれます。
上に示したトライ木の各頂点に対して failure
の行き先を探索し、 PMA
を構築すると次の図のようになります。青い有向辺が failure
を表しています。
本問題ではトライ木を構築し、failure
を適切に引くことで PMA
の構築をおこなってもらいます。
最初に次のような Node
クラス、 AhoCorasick
クラスを作成してください。問題「トライ木の構築」 で作成した Trie
クラスを変更すると良いです。
Nodeクラス //PMAの各頂点を表すクラス
-----------------------------------
メンバ変数
child[ch]: chをキーとして、頂点を返す連装配列 //文字 ch に対する遷移
failure: Node //failure の遷移先の頂点
is_pattern: bool //この頂点はパターンを受理するか(trueなら受理する)
AhoCorasickクラス //PMA全体を表すクラス
-----------------------------------
メンバ変数
root: Node //トライ木の根を表す
-----------------------------------
メンバ関数
insert(pattern: string): void //引数とする文字列 pattern をトライ木に挿入する
build(): void //トライ木の各頂点に failure を引いて PMA にする (本問題で実装)
insert()
はトライ木に文字列を格納する処理です。build()
は次のような処理をおこないます。・根から到達できる全ての頂点とその対応する文字列を列挙する.
たどり着いた頂点では以下の処理をおこなう.
1. 頂点 S にたどり着いたなら, S を除く S の接尾辞を全て列挙する.
2. 列挙した接尾辞の対応する頂点がグラフ内に存在するかを調べる.
3. 存在する頂点の中で最も対応する文字列が長いものを頂点 S の failure の行先とする.
build()
を実行して PMA
を構築してください。failure
の行き先となる頂点の名前を出力してください。ただし、行き先が根である場合は EPS
と出力してください。 S
合計で |S| 行の出力を行います。
i 行目には深さ i の頂点の failure
の行き先となる頂点の名前を 1 行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて, 以下の条件をみたします
・1 ≦ |S| ≦ 200 (|S| は、S の文字数です。)
abab
EPS
EPS
a
ab
aaaaa
EPS
a
aa
aaa
aaaa
abcdefg
EPS
EPS
EPS
EPS
EPS
EPS
EPS