Z algorithm, KMP法(MP法), BM法を実装した

2023/05/04初版公開
atcoderやってます。緑です。python使ってます。

アルゴリズムの紹介・解説は書きません。これから実装しようとしている人向けに感想・役に立つかもしれない情報を記します。

まず、これらのアルゴリズムを実装するのは大変でした。解説をみればやってることはなんとなくわかりますが、実装するとなると難易度が上がりました。 seg木を実装した時の5倍の時間 × 3(種類のアルゴリズム) がかかりました。初歩的なアルゴリズムなのに実装できない!ってなってる人はこの記事を見て安心してください。

実装したアルゴリズムが正しく動くかどうかは AOJ-ALDS-14-Bで確認できます。
(BM法は最悪計算量を改善しない限りTLEになる可能性大)
またZ-algorithmはLibrary-checkerでも確認できます。

これから実装する人には、以下の手順をお勧めします。
①各アルゴリズムのいろいろなバリエーションをなんとなく理解する。
②自分が(最終的に)どのバリエーションを実装するのか決める
③はじめは一番簡単そうな種類を実装し、ちゃんと動作することを確認して次に簡単そうなverを実装する

①について、以下のキーワードがなんとなくわかってればいいと思います。
KMP：O(N^2)の前処理とO(N)の前処理, Knuth's trick
BM：不一致ルール(bad character rule), 接尾語一致ルール(strong good suffix rule), O(N^2)の前処理とO(N)の前処理, 最悪計算量をO(N)に改善できる
Z-algo：KMP法、BM法の前処理に使える。またKMP,BMと同じくO(N)の検索アルゴリズムとしても機能する

BM法に関しては不一致ルールしか考慮していない記事が多く、接尾語一致ルールに触れている記事もパターンの先頭部分と末尾部分が一致する場合の処理まで言及していない記事が多いです。この解説記事に完全版のBM法がとても詳しく載っています。長いですが流し読みすれば雰囲気はつかめるはずです。

Z-algorithmに関しては、頭が悪くても理解できる記事を見つけるのが大変でした。解説記事が豊富ではなく理解するのが難しいですが、アルゴリズム自体はシンプルです。この解説動画で7分程度の簡単な解説がなされてます。解説の中で一番わかりやすかったです。名前もかっこいいしアルゴリズムもかっこいいので好きです。

苦労して実装しましたが、競プロではローリングハッシュで十分な場面が多そうで使用頻度は低そうです。z-algorithmはたまに便利かもですが。

コードは冗長になりそうなので載せません。Z-algorithmを用いた前処理とか、接尾語一致ルールを取り入れたBM法とか調べた限りない(頑張って探せばたぶんいくらでもある)のでコード載せたら喜ぶ人いるんですかね？そもそもこのブログを見てる人がほとんどいませんが。