忍者ブログ
  • 2019.09
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 2019.11
KMPアルゴリズム
atcoder141Eを解いていたら良い方法が思い浮かばず、解説読んでKMPアルゴリズムを知った。

E - Who Says a Pun?


KMP法(by wikipedia)
これの面白いところは、BM法と違いは何文字一致したかまで確認出きるという点かな。
勉強になったなり。
ちなみに、解説にはZアルゴリズムとあったのだけども、すべての部分文字列について知りたいわけではないので、KMPのテーブル生成のみに着目したほうがパフォーマンスは良さげ。
しゃくとり法を使うともっとシンプルに解けていることが衝撃である。
PR
【2019/09/16 18:44 】 | atcoder | 有り難いご意見(0)
                                    
<<赤黒木をgoで実装してみた | ホーム | javascriptのflatMapとpythonの内包表記>>
有り難いご意見
貴重なご意見の投稿














<<前ページ | ホーム | 次ページ>>