あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

snuke.hatenablog.com上の記事では記事中の注釈の通りMPを紹介したので、KMPとは何かを大雑把に解説しておきます。 KMPは、上の記事で紹介したMP（Morris-Pratt）にKnuthパワーが加わったものです。 さらなる考察がされて、文字列検索の効率が向上した感じです。 計算量的な面でも、全体計算量は線形のままですが、後述す…