AGC047-Bを機に入門するTrie木(+ロリハの衝突について)

この記事の概要
前提知識
Trie木で出来ること(基本編)
実現方法
実装
Trie木で出来ること(応用編)
AGC047-Bの解法について(ネタバレ注意)
余談(ロリハの衝突について)
終わりに

AGC047-Bはこれ↓

https://atcoder.jp/contests/agc047/tasks/agc047_b

この記事の概要

上の問題はTrie木が想定の問題なのれふが, コンテスト後のTLを見るにTrie木が手元に無い人が多いようなので, 書くことにした次第れふ.

使用頻度は高くないれふが, あまり難しくないと思っているので持っておくと嬉しいかも……？

前提知識

根付き木をDFSして×××する問題に抵抗があると大変かもしれません.

問題例

https://atcoder.jp/contests/abc138/tasks/abc138_d

https://atcoder.jp/contests/dp/tasks/dp_p

Trie木で出来ること(基本編)

Trie木はいろんなことが出来るので, これらが基本的な機能の例として適切かは怪しい…れふが, とりあえずこの2つを挙げておきまふ.

add(string S) 文字列SをO(|S|)で追加する
find(string S) Sが以前に追加されたか否か, および何番目に追加されたかをO(|S|)で調べる.

実現方法

文字列に対し, イテレータが指す位置をノード, 文字を辺に対応させた根付き木を作りまふ. 先頭の位置が根れふ. ここで, prefixが同じ文字列はノードを共有することによって, 1つのノードから生える辺数は文字種の数で抑えられまふ.

初めは根のみの根付き木で, addのたびに必要に応じてノードを増やしまふ.

たとえば, "trie", "tree"をこの順に追加すると, trie木はこんな感じになりまふ.

f:id:SayakaAmemiya:20200810194726p:plain

実装

大体こんな感じのものがあれば良いはず……

node構造体

文字種がa～zの26種類とすると, vector<int> nextNode(26)(a,b,...,zに対応する辺の移動先のノードの番号を持つ. 存在しなければ-1), int value(何番目に追加された文字列の終端かを持つ. 文字列の終端でなければ-1)を持っておけばひとまず良いれふ. (コンストラクタでvectorの要素数を変えたり, 文字種に対する対数オーダーを犠牲にmapで持ったりとか色々工夫の余地はありまふが)

node構造体を持つ配列

void add(string &S, int currentPos = 0, int currentNode=0);

必要に応じてノードを増やしながら, Sを追加しまふ.

int find(string &S,int currentPos=0, int currentNode = 0);

辺をたどって, Sの末尾まで行ったらそのノードのvalueを返しまふ.

int encode(char c);

a～zを0～25に変換する関数れふ. (必須ではないれふ)

問題例

https://yukicoder.me/problems/no/430

https://atcoder.jp/contests/joisc2010/tasks/joisc2010_dna

Trie木で出来ること(応用編)

Trie木に対し, 根付き木に対してよくやるような操作を行うことで問題が解けることがありまふ. その方法は, ノードに持たせるvalueを適当に変える・addやfindの際にいろいろ処理する・新たに再帰関数を作って何かしらさせる, などいろいろ思いつきまふが, まあお好みで……

例えば, 「 $N$ 個の文字列 $s_1,s_2,...,s_N$ が与えられる. これらはカウンターを持っていて, はじめ, すべての文字列のカウンターは0である. $Q$ 回操作をする. $i$ 回目の操作では, $t_i$ をprefixに持つ文字列のカウンターの値を $x_i$ 増やす. 操作後の各文字列のカウンターの値は？(制約 $\sum{s_i} \le 10^6, \sum{t_i} \le 10^6)$ 」という問題は, $s_1,s_2,...,s_N$ を追加したTrie木に対して冒頭で紹介したKi(https://atcoder.jp/contests/abc138/tasks/abc138_d?lang=ja)と同じ解法を適用すれば解くことができまふ.

問題例(この後解説するAGC-Bの方が簡単だと思いまふ)

https://atcoder.jp/contests/tenka1-2016-final/tasks/tenka1_2016_final_c

https://atcoder.jp/contests/arc087/tasks/arc087_c

AGC047-Bの解法について(ネタバレ注意)

改めて問題のリンクを…

https://atcoder.jp/contests/agc047/tasks/agc047_b

以上で示した, Trie木ができることを踏まえ, いろいろ考察すると大体こんな感じになりまふ.

文字列を全部反転し, 長さの昇順に並べ替える
1文字目以降, 2文字目以降, ...に含まれる文字の集合を求めて, dfsでいい感じにやる
最後の文字を除いて, Trie木に追加(valueとして最後の文字に対応する個数を持たせる)

詳しくはこれを見てください.

https://atcoder.jp/contests/agc047/submissions/15809887

余談(ロリハの衝突について)

この問題は, Trie木に文字列をaddする代わりにその文字列のローリングハッシュを文字数ごとにmapで持ってやっても解けまふ. (定数倍が大変らしいれふが)

ただし, modが10⁹程度の素数一つのロリハを使うと, 衝突が発生してWAとなるようれふ. (そういう人をTLで多く見かけた)

この現象は, 次のようなケースを考えると分かりやすいと思われまふ.

長さ10で最後の文字がaの文字列50000個と, 長さ11で最後の文字がaの文字列30000個からなるケース

このケースは, 50000×30000個の文字列の組それぞれに対し, 異なる文字列の組に対して異なるハッシュの組を返す必要がありまふ. ハッシュの値が一様に分布していると仮定すると, ある異なる文字列の組に対してハッシュ値が一致してしまう確率は, 取りうる値の個数の逆数となりまふ. このことを考えると, 10⁹オーダーの素数一つでは力不足でしょう.

同様の問題として, 次のような問題がありまふ.

https://www.hackerrank.com/contests/kiritan-birthday-contest-2020/challenges/zundamochi/problem

10⁹オーダーの素数一つによるローリングハッシュは, 「文字列Sの部分文字列として文字列Tは何回現れるか」というような, 判定する組の個数が文字列長に対して線形な場合は基本衝突しませんが, この問題のように組の個数が文字列長の2乗オーダーの時, 誕生日のパラドクスと同様の現象により, 衝突してしまいまふ.

このような状況はままあるので, mod一つのロリハを使う場合はよく組の個数を見積もることが重要れふ.

終わりに

彼氏募集中れふ. (コロナ禍で出会いが……)