String matching problem 文字列照合

ある文字列（テキスト）に対して、指定された照合文字列（パタン）の存在を発見するための機能は、多くのテキストエディタに実装されています。「テキストが変更中のドキュメントで、パタンがユーザーが探したい特定のキーワード」というのが典型的な例でしょう。

この文字列照合問題のための効率の良いアルゴリズムは、テキストエディタのプログラムには不可欠です。また、文字列照合アルゴリズムは、ＤＮＡ配列中の特定のパタンを発見したり、インターネットにおけるキーワード検索など、様々な場面で応用されます。

文字列照合問題は以下のように形式化されます。
文字列 T[n] を長さ n のテキスト、文字列 P[m] を長さ m のパタンとし、T と P の各要素はある有限の集合 S に属するとします。例えば、S = {0, 1}、S = {0, 1, 2, ..., a, b, ... z} などが考えられます。

「 0 ≦ i ≦ n - m 」 かつ 「 0 ≦ j ≦ m - 1 について P[j] = T[i + j] 」を満たすとき、「テキスト T の i の位置にパタン P が存在する」と言います（下図参照）。

例: i = 3 P[0] = T[3 + 0] = T[3] P[1] = T[3 + 1] = T[4] P[2] = T[3 + 2] = T[5]

文字列照合問題は、テキストの中に存在する指定されたパタンの全ての位置を発見する問題です。

これから紹介していこうと思うアルゴリズムです↓

• Brute-force algorithm 力任せの文字列照合アルゴリズム
• Knuth-Morris-Pratt (KMP) algorithm
• Boyer-Moore algorithm