|
atcoder141Eを解いていたら良い方法が思い浮かばず、解説読んでKMPアルゴリズムを知った。
E - Who Says a Pun? KMP法(by wikipedia) これの面白いところは、BM法と違いは何文字一致したかまで確認出きるという点かな。 勉強になったなり。 ちなみに、解説にはZアルゴリズムとあったのだけども、すべての部分文字列について知りたいわけではないので、KMPのテーブル生成のみに着目したほうがパフォーマンスは良さげ。 しゃくとり法を使うともっとシンプルに解けていることが衝撃である。
PR |
 |
|
|
|
|
|
忍者ブログ [PR] |
