(0:44) darts-cloneはDAWG (Directed Acyclic Word Graph) というデータ構造を使っていたのか。
そういえば、これまで何度も目にする機会はあったはずなのに頭に残っていなくて、なんとなくダブル配列を使っているような気分になっていた。
ダブル配列は元のdartsのほうだな。
DAWGについてはこの連休あたりに調べてみよう。
メモ。
Directed Acyclic Word Graph or DAWG
http://www.comp.nus.edu.sg/~ksung/thesis/DoHH_thesis2013.pdf
http://www-igm.univ-mlv.fr/~mac/REC/text-algorithms.pdf
それにしても、darts-cloneの参考文献はダブル配列のばっかりだな。
最後のひとつだけDAWGのものだ(読めないけど)。
ぼくがdarts-cloneのことをダブル配列ベースだと勘違いしたのもあながち無理ではないっぽい。
ところで、休日はいいけど平日はRailsの勉強中(なかなか進まない)だ。
どうしようかな。
今からスペイン語の暗記。
どうしても遅くなってしまうな。