|
AGC039に参加して問題Bが解けなかったのだけども、解き方が分かったので解説
問題としては、同じVnに辺があってはいけないというもの。 幅優先探索法で、既に探索済みのノードに出会った場合、次のレベルか前のレベルかしかないということに気づけば後はもっとも長いパスを見つければOK うーん、時間中には思いつかん。。。
PR |
 |
|
atcoder141Eを解いていたら良い方法が思い浮かばず、解説読んでKMPアルゴリズムを知った。
E - Who Says a Pun? KMP法(by wikipedia) これの面白いところは、BM法と違いは何文字一致したかまで確認出きるという点かな。 勉強になったなり。 ちなみに、解説にはZアルゴリズムとあったのだけども、すべての部分文字列について知りたいわけではないので、KMPのテーブル生成のみに着目したほうがパフォーマンスは良さげ。 しゃくとり法を使うともっとシンプルに解けていることが衝撃である。
|
|
|
| ホーム |
忍者ブログ [PR] |
