メモ書き
普通に Trie 生やしたあと今見てるノードの表す文字列の suffix のうち辞書の文字列の prefix として存在するようなものの中で最も長いものに link を繋ぐ
というのは知っていたが, なぜこれで上手くいくのかさっぱりわかっていなかった
例えば辞書が abcd, b, bce で見たい文字列が abce だったら abc まで行ったらつぎに bc のところに飛ぶのはわかるがそうすると b をスルーしないか？ と思っていた
これの対処法は, ab まで見たときにもう b をチェックすることになる
どうすればいいのかというと, 各ノードについて, suffix link の先のものもそこにあったことにすればいい
つまり, suffix link を構築するときに辞書に対応するノードにマークをつけておくが, そのノードの suffix link の先のマークも書き加える
そうすれば, 今のノードの文字列の suffix に対応する部分も全て拾える 頭がいい
構築は 0 から bfs をしていって, 自分の suffix link の次は 自分の次の suffix link ですみたいに埋めていけばいい
これだけなので実装はとても軽くて, Trie を書くところから始めてもそんなにかからなかった
