文字列の中から効率良くキーワードを探し出せ力任せ法の場合を考えます。左から順に1文字ずつ比較すると「abab」まで一致しています。次の文字は、文字列では「a」、検索ワードでは「c」となり不一致です。そこで、文字列のポインタを1つ進めて2文字目の「b」、検索ワードの先頭「a」から比較を始めます。 5文字目まで進んだ文字列側のポインタが、2文字目まで戻りました。これは実に無駄です。 「abab」まで一致していることが確かめられています。ということは3、4文字目の「ab」は、検索ワードの先頭の2文字「ab」と一致しており、文字列の5文字目と検索ワードの3文字目から比較を継続してもよいはずです。 このように検索ワードのどの位置で不一致になったかを把握することによって、どこから比較を再開すればよいかをあらかじめ決めることができます。文字列側のポインタを戻さなくて済みます。 この文字列探索アルゴリズムがKMP法です。KMPとは、このアルゴリズ
