文字列の検索

文字列検索とは、テキストの文字列内に、パターンの文字列と一致する部分文字列が存在するかどうかを調べ、存在したならば、その位置を求めるという操作です。例えば、
　　　テキストの文字列が「ｄａｂｄａｂｃａｂｃｂａ」
　　　パターンの文字列が「ａｂｃｂ」
の場合
　　　　　　　　　　　　　　　　　　　１１
　　　　　　　　　０１２３４５６７８９０１
　　　テキスト：　ｄａｂｄａｂｃａｂｃｂａ
　　　パターン：　　　　　　　　ａｂｃｂ
となるので７を戻し、パターンが「ａｂｃｘ」の場合は、テキストに一致する部分文字列が存在しないので、－１を戻す関数を考えます。

以下、テキストは配列ｔ、パターンは配列ｐに入っており、テキストの文字列長さをｎ、パターンの文字列長さをｍとします。上の例では、
　　　t[0]="d", t[1]="a", … , t[11]="a"　　n=12
　　　p[0]="a", p[1]="b", … , p[3]="b" 　　m=4
となります。（ｔ、ｐは０から始まり、ｎ、ｍは個数であることに注意）
　なお、プログラムでは、これらの値はグローバル変数として定義されているものとします。

単純比較法

単純比較法は、テキストとパターンを１文字ずつ比較していく方法です。わかりやすいのですが、最悪の場合、ｍ×ｎ回の比較を行う（計算量オーダーが Ｏ(ｎ×ｍ) になる）ため、非効率な方法です。

プログラム

ア　function simple() {
イ　　　var i, j;
ウ　　　for (i=0; i<=n-m; i++) {
エ　　　　　for (j= 0; j<m; j++) {
オ　　　　　　　if (t[i+j] != p[j]) break;
カ　　　　　}
キ　　　　　if (j == m) return i;
ク　　　}
ケ　　　return -1;
コ　}

アルゴリズム

ｔ[ｉ]以降とｐが一致しているかを調べるには、ｐのｊ番目の文字ｐ[ｊ]とｔ[ｉ＋ｊ]を比較することが基本になります（オでの比較）。
下表では、ｉ＝３、ｊ＝２（ｉ＋ｊ＝５）のとき、ｔ[５]＝ｂとｐ[２]＝ｃを比較しています。
　　　　　　ｉ　i+j 　n-m　ｎ
　　　　　　↓　↓　　↓　　　↓
　　　０１２３４５６７８９101112
ｔ：　ｄａｂｄａｂｃａｂｃｂａ
ｐ：　　　　ａｂｃｂ
　　　　　　　　↑
　　　　　　　　ｊ

一致していないならば、それ以上この位置で比較する必要はないので、ｐ全体を右に一つ移動させ（ｉに１を加えて）ｐの先頭から（ｊ＝０として）比較します（オのbreak）。
一致していれば（図では一致していないが）、ｊに１を加えて、ｔ[６]＝ｃとｐ[３]＝ｂと比較します。

キで ｊ＝ｍ のときに打ち切っているのは、パターンのすべての文字が一致したときは、ｊ＝ｍ－１であり、それがｊ＝ｍになったときにエ～カのループから出てキへ行くからです。

ウで ｉ≦ｎ－ｍ（１２－４＝８）としたのは、ｉ＝９になると、ｐが最期までいったとき（ｊ＝３になったとき）に、ｉ＋ｊ＝１２となり、オで ｔ[ｉ＋ｊ] がｔの配列上限を超えてしまう（オーバーフローする）からです。

トレース

ｉはｔの要素番号、ｊは比較するｐの要素番号。ｉ＋ｊが比較位置

ｉ　ｊ i+j　０１２３４５６７８９０11
　　　　　　ｄａｂｄａｂｃａｂｃｂａ
０　０　０　ａｂｃｂ　　赤字は不一致を示す→ｉに１を加えｊを０にする
１　０　１　　ａｂｃｂ　青字は一致を示す→ｊに１を加える
１　１　２　　ｂａｃｂ
１　１　３　　ａｂｃｂ
２　０　２　　　ａｂｃｂ
３　０　３　　　　ａｂｃｂ
４　０　４　　　　　ａｂｃｂ
４　１　５　　　　　ａｂｃｂ
４　２　６　　　　　ａｂｃｂ
４　３　７　　　　　ａｂｃｂ
５　０　５　　　　　　ａｂｃｂ
５　１　６　　　　　　　ａｂｃｂ
７　０　７　　　　　　　　ａｂｃｂ
７　１　８　　　　　　　　ａｂｃｂ
７　２　９　　　　　　　　ａｂｃｂ
７　３　10　　　　　　　　ａｂｃｂ　　すべて一致
└　一致位置（戻す値）

計算量

ウでｉをｎ－ｍ回行い、エでｊをｍ回行っています。もし、一致する部分文字列が存在しなかったときは、オがすべてのｉ、ｊの組合せで行うことになり、その比較回数は、(ｎ－ｍ)×ｍ回になります。ｎに対してｍが小さいなら、約ｎ×ｍ回の比較になります。それで、この方法の計算量オーダーは Ｏ(ｎ×ｍ) になります。

力任せ法（brute force aigorithm）

この方法も単純比較法と同じように１文字ずつ比較する方法で、計算量もほぼ同じですが、「力任せ法」と名前がついているように、よく知られたアルゴリズムです。以降のＫＭＰ法やＢＭ法と構造が似ているので、これを理解しておくと、それらの方法の理解に役立ちます。

プログラム

ア　function bf() {
イ　　　var i, j;
ウ　　　i = 0;
エ　　　j = 0;
オ　　　while (i <= n-m) {
カ　　　　　while ( (i < n) && (j < m) ) {
キ　　　　　　　if (t[i] == p[j]) {
ク　　　　　　　　　i++;
ケ　　　　　　　　　j++;
コ　　　　　　　}
サ　　　　　　　else {
シ　　　　　　　　　i = i - j + 1;
ス　　　　　　　　　j = 0;
セ　　　　　　　}
ソ　　　　　}
タ　　　　　if (j == m) return i-j;
チ　　　}
ツ　　　return -1;
テ　}

アルゴリズム

単純比較法では、ｐ[ｊ]とｔ[ｉ＋ｊ]とを比較していました。すなわち、ｉは配列ｔのｉ番目という意味で用いていました。それに対して力任せ法では、キからわかるように、ｉは、比較を行う位置を示しています。
　一致したとき（キ～コ）：次の文字の比較をするために、ｉとｊに１を加えます。
　不一致のとき（サ～セ）：ｊ＝０とするのは、単純比較法と同じです。シで、ｉ＝ｉ－ｊ＋１としているのは次の理由です。
　下図の「現在」において、i＝７、ｊ＝３のときに、ｔ[ｉ]＝ａ、ｐ[ｊ]＝ｃで不一致になりました。「現在」でのｐの先頭位置は４（＝ｉ－ｊ）にあるので、「次」では１だけ移動させて５にする必要があります。すなわち、次のｊはｉ－ｊ＋１になります。
　　　現在　　　　ｉ－ｊ　ｉ
　　　　　　　　　　│　　│ 　　　ｉ：　０１２３４５６７８９101112
　　　ｔ：　ｄａｂｄａｂｃａｂｃｂａ
　　　ｐ：　　　　　ａｂｃｂ
　　　ｊ：　　　　　０１２３
　　　　　　　　　　　　　│
　　　　　　　　　　　　　ｊ

　　　次　　　　　ｉ－ｊ＋１
　　　　　　　　　　　│
　　　ｉ：　０１２３４５６７８９101112
　　　ｔ：　ｄａｂｄａｂｃａｂｃｂａ
　　　ｐ：　　　　　　ａｂｃｂ
　　　ｊ：　　　　　　０１２３

タで、一致したことがわかり、その戻す値がｉ－ｊなのは、次の理由です。
　　　現在　　　　　　　ｉ－ｊ　ｉ
　　　　　　　　　　　　　│　　│
　　　ｉ：　０１２３４５６７８９101112
　　　ｔ：　ｄａｂｄａｂｃａｂｃｂａ
　　　ｐ：　　　　　　　　ａｂｃｂ
　　　ｊ：　　　　　　　　０１２３
　　　　　　　　　　　　　　　　│
　　　　　　　　　　　　　　　　ｊ
　すべての文字が一致したのは、ｊ＝３（＝ｍ－１）のときに、キが成立したときです。クでｉ＝１０＋１＝１１、ケによりｊ＝４（＝ｍ）になり、タに到達します。そして、戻す値は７（「現在」でのｉ－ｊ）になります。タに達したときのｉとｊは、「現在」よりも１多いので、戻す値は「(ｉ－１)－(ｊ－１)」なのですが、これを計算すると、ｉ－ｊになります。

高速化の考え方

力任せ法では、無駄な比較をしています。例えば、
　　　現在　　　　ｉ－ｊ　ｉ
　　　　　　　　　　│　　│
　　　ｉ：　０１２３４５６７８９101112
　　　ｔ：　ｄａｂｄａｂｃａｂｃｂａ
　　　ｐ：　　　　　ａｂｃｂ
　　　ｊ：　　　　　０１２３
　　　　　　　　　　　　　│
　　　　　　　　　　　　　ｊ
で、ｔ[７]≠ｐ[３]となったときを考えます。力任せ法では、
　　　ｉ：　０１２３４５６７８９101112
　　　ｔ：　ｄａｂｄａｂｃａｂｃｂａ
　　　ｐ：　　　　　　ａｂｃｂ
　　　ｐ：　　　　　　　ａｂｃｂ
のように、ｐの位置を１つずつ右にずらして、再度比較をしていきます。
　しかし、「現在」の時点で、ｔ[ｉ－ｊ＋１]＝ｔ[５]＝ｂ、ｔ[ｉ－ｊ＋２]＝ｔ[６]＝ｃであることがわかっているのですから、ｐ[０]＝ａとｔ[５]＝ｂやｔ[６]＝ｂを比較する必要はなく、次のように、ｔ[７]から比較をすればよいことになります。
　　　ｉ：　０１２３４５６７８９101112
　　　ｔ：　ｄａｂｄａｂｃａｂｃｂａ
　　　ｐ：　　　　　　　　ａｂｃｂ

ここで重要なことは、ｐの先頭位置はｉ－ｊなのですから、ｐの位置をｋ個右にずらすということは、ｉ－ｊの値をｉ－ｊ＋ｋにするということです。
　力任せ法で「ｔ[ｉ]≠ｐ[ｊ] になったら、ｐの位置を１つ右にずらす」のは、シで「ｉ＝ｉ－ｊ＋１」としたからです。
　あらかじめ、ｐの文字列を調べて、「ｉ＝ｉ－ｊ＋ｆ[ｊ]から比較を行う」というような配列ｆを作成しておけば（上の例で、ｆ[３]＝２となっていれば、ｉ＝ｉ－ｊ＋ｆ[ｊ]＝７－３＋３＝７なので、次は ｔ[７] から比較する）、比較回数を減少させることができます。
　その代表的な方法に後述のＫＭＰ法とＢＭ法があります。

ＫＭＰ法（Knuth-Morris-Pratt algorithm）

ＫＭＰ法では、「ｐ[ｊ] の位置で不一致になったとき、何文字ずらして再開するか」に着目して、それをあらかじめ表（配列next）にしておきます。
　ＫＭＰ法の特徴は、力任せ法と異なり、テキストの比較で後戻りをしない（ｔ[ｉ] のｉを小さくするステップがない）ことです。すなわち、最悪の場合でもｎ回の比較ですみます。それで計算量のオーダーは Ｏ(ｎ) となります（next を設定するための比較回数がかかりますが、ｍはｎに対して非常に小さいのが通常ですから、無視することができます）。
　テキストの比較で後戻りしないために、テキストが非常に大きく、メモリに格納できず、ファイルから読み込んで処理をすることができます。

プログラム

ア　function kmp() {
イ　　　var i, j;
　　　/* ずらす表 next[j] の作成 */
ウ　　　next = new Array(11);
エ　　　next[0] = 1;
オ　　　for (j=1; j<m; j++) {
カ　　　　　for (k=1; k<j; k++) {
キ　　　　　　　jj=k;
ク　　　　　　　while ( (jj<j) && (p[jj] == p[jj-k]) ) jj++;
ケ　　　　　}
コ　　　　　next[j] = k;
サ　　　}
　　　/* ｔとｐの比較 */
シ　　　i = 0;
ス　　　j = 0;
セ　　　while ( (i < n) && (j < m) ) {
ソ　　　　　if (t[i] == p[j]) {
タ　　　　　　　i++;
チ　　　　　　　j++;
ツ　　　　　}
テ　　　　　else {
ト　　　　　　　j = j - next[j];
ナ　　　　　　　if (j < 0) {
ニ　　　　　　　　　i++;
ヌ　　　　　　　　　j++;
ネ　　　　　　 }
ノ　　　　　}
ハ　　　}
ヒ　　　if (j == m) return i - m;
フ　　　else return -1;
ヘ　}

アルゴリズム（シ～フ）

前半（ウ～サ）は、next[ｊ] を設定するプロセスです。これに関しては、かなり複雑なので後述することにして、ともかく、次のように設定されたこととします。
　　　next[０]＝１，next[１]＝１，next[２]＝２，next[３]＝３

後半（セ～ホ）は、ｔとｐとの比較をするプロセスです。
　ここでのセ～ハは、力任せ法のカ～ソとよく似ています。
　ｔ[i]＝ｐ[j] の場合はまったく同じです。
　ｔ[i]≠ｐ[j] の場合は、
　　　力任せ法：ｉ＝ i - j + 1;　j = 0;
　　　ＫＭＰ法：ｊ＝ｊ－next[ｊ]； 　　　　　　（ｊ＜０のときは、ｉ，ｊに１を加える）
が異なるだけです。

先に「ｐの位置をｋ個右にずらすには、ｉ－ｊをｉ－ｊ＋ｋにする」といいました。トでｊの値をｊ－next[ｊ] にすることは、ｉ－ｊをｉ－ｊ＋next[ｊ] にすることですから、これは、ｐの先頭位置を next[ｊ] だけ右に移動せよということになります。
例えば、
　　　現在　　　　ｉ－ｊ　ｉ
　　　　　　　　　　│　　│
　　　ｉ：　０１２３４５６７８９101112
　　　ｔ：　ｄａｂｄａｂｃａｂｃｂａ
　　　ｐ：　　　　　ａｂｃｂ
　　　ｊ：　　　　　０１２３
　　　　　　　　　　　　　│
　　　　　　　　　　　　　ｊ
　次のｊ：　　　　　　　　ａｂｃｂ
で、現在のｐの先頭位置は４です。ｉ＝７、ｊ＝３で不一致になったとき、next[３]＝３であるとすれば、ｊ＝ｊ－next[ｊ]＝３－３＝０ になります。そして、次にソで比較するのは、ｔ[７]＝ａとｐ[０] です。すなわち、ｐをnext[３]＝３だけ右に移動したことになります。
　なお、ナ～ネでの、「ｊ＜０のとき」は、ｐ[０] との比較で不一致になったとき、次にｐ[－１]とｔ[ｉ－１] を比較することを避けるためです。

力任せ法では、while のループが２重になっていました。それで、Ｏ(ｎ×ｍ) の計算量になったのです。
それに対して、ＫＭＰ法では１つのループになっており、次のトレースのように、比較位置が減少することがありません。それで、計算量は Ｏ(ｎ×ｍ) になります。

トレース

ｉは比較位置、ｊはｐの要素番号、赤字は不一致、青字は一致を示す。

ｉ　ｊ　next[ｊ]　０１２３４５６７８９1011
　　　　　　　　　ｄａｂｄａｂｃａｂｃｂａ
０　０　　１　　　ａｂｃｂ　　ｊ＝０－１＜０なので、ｉ＋１＝１、ｊ＋１＝０
１　０　　１　　　　ａｂｃｂ
２　１　　１　　　　ａｂｃｂ
３　２　　２　　　　ａｂｃｂ　　　ｊ＝２－next[2]＝０≧０、next[2]＝２だけ右へ
３　０　　１　　　　　　ａｂｃｂ　　　ｊ＝０－１＜０→ｉ＝４、ｊ＝０
４　０　　１　　　　　　　ａｂｃｂ
５　１　　１　　　　　　　ａｂｃｂ
６　２　　２　　　　　　　ａｂｃｂ
７　３　　３　　　　　　　ａｂｃｂ
７　０　　１　　　　　　　　　　ａｂｃｂ
８　１　　１　　　　　　　　　　ａｂｃｂ
９　２　　２　　　　　　　　　　ａｂｃｂ
10　３　　３　　　　　　　　　　ａｂｃｂ
　　　　　　　　　　　　　　　　└　一致位置＝7

アルゴリズム（ウ～サ）

ｐ＝ａｂｃｂの場合に、next[０]＝１，next[１]＝１，next[２]＝２，next[３]＝３と設定した理由は、上の説明で理解できたと思います。
　以降、それを設定するアルゴリズムの説明をします。

上の例では、ｐが短く同じ文字が少なくわかりにくいので、
　ｐ＝ａbｃａｂｂｃ
とします。
　next は次のようになります。
　　　　ｊ　：　０　１　２　３　４　５　６
　　　ｐ[ｊ]：　ａ　ｂ　ｃ　ａ　ｂ　ｂ　ｃ
　　next[ｊ]：　１　１　２　３　３　３　６
　ここで、どこのａかｂかわかりにくいので、必要に応じて、a0, b1, c2, a4, …, c6 と表記します。

●ａ０：
　　　ｉ：　0　1　2　3　4　5　…
　　　ｔ：　-　-　x　?　?　?　…
　　　ｐ：　　　　a0 b1 c2 …
　　　　　　　　　└ここで不一致
先頭位置で不一致のときは、無条件で１つ右へ移動し、ａ０から比較を再開します。→next[０]＝１
　　　ｉ：　0　1　2　3　4　5　…
　　　ｔ：　-　-　x　?　?　?　…
　　　ｐ：　　　　　 a0 b1 c2 …
　　　　　　　　　　 └ここから比較

●ｂ１：
　　　ｉ：　0　1　2　3　4　5　…
　　　ｔ：　-　-　a　x　?　?　…
　　　ｐ：　　　　a0 b1 c2 …
　　　　　　　　　　 └ここで不一致
ｘがａかも知れないので、１つ右へ移動し、ａ０から比較を再開します。→next[１]＝１
　　　ｉ：　0　1　2　3　4　5　…
　　　ｔ：　-　-　a　x　?　?　…
　　　ｐ：　　　　　 a0 b1 c2 …
　　　　　　　　　　 └ここから比較

●ｃ２：
　　　ｉ：　0　1　2　3　4　5　…
　　　ｔ：　-　-　a　b　x　?　…
　　　ｐ：　　　　a0 b1 c2 …
　　　　　　　　　　 　 └ここで不一致
ｘがａかも知れないので、２つ右へ移動し、ａ０から比較を再開します。→next[２]＝２
　　　ｉ：　0　1　2　3　4　5　…
　　　ｔ：　-　-　a　b　x　?　…
　　　ｐ：　　　　　　　a0 b1 c2 …
　　　　　　　　　　　　└ここから比較

●ａ３：
　　　ｉ：　0　1　2　3　4　5　6　…
　　　ｔ：　-　-　a　b　c　x　?　…
　　　ｐ：　　　　a0 b1 c2 a3 b4 …
　　　　　　　　　　 　 　 └ここで不一致
ｘがａかも知れないので、３つ右へ移動し、ａ０から比較を再開します。→next[３]＝３
　　　ｉ：　0　1　2　3　4　5　6　…
　　　ｔ：　-　-　a　b　c　x　?　…
　　　ｐ：　　　　　 　 　 a0 b1 c2 a3 b4 …
　　　　　　　　　　 　 　 └ここから比較→next[２]＝２
ここまでで、ｐ[１]～ｐ[ｊ－１] にｐ[ｋ]＝ｐ[ｊ] となる文字が存在しないときは、next[ｊ]＝ｊとればよいことがわかります。
また、比較を再開するｔの位置は、不一致が発生したところからであることもわかります。

●ｂ４：
　　　ｉ：　0　1　2　3　4　5　6　7　…
　　　ｔ：　-　-　a　b　c　a　?　?　…
　　　ｐ：　　　　a0 b1 c2 a3 b4 b5 …
　　　　　　　　　　 　 　 　 └ここで不一致
このときには、単純に４つずらすと、次のようになります。
　　　ｉ：　0　1　2　3　4　5　6　7　…
　　　ｔ：　-　-　a　b　c　a　x　?　…
　　　ｐ：　　　　　 　 　 　 a0 b1 c2 a3 b4 b5 …
ところがｔの５がａですから、ａ０をそこに合わせる必要があります。そして、そこでは既に一致していることがわかっているので、ｂ１から（すなわち、ｔの現在位置（６）から）比較を再開することになります。→next[４]＝３
　　　ｉ：　0　1　2　3　4　5　6　7　…
　　　ｔ：　-　-　a　b　c　a　x　?　…
　　　ｐ：　　　　　 　 　 a0 b1 c2 a3 b4 b5 …
　　　　　　　　　　 　 　 　 └ここから比較
この next[４]＝３を探すには、次のように考えます。
ｐ[４] で不一致だということは、ｐ[０]～ｐ[３] はｔと一致していたことになります。
比較位置の一つ手前（５）ｐ[３]＝ａですから、ａ０を５の位置まで移動させることになります。

●ｂ５：
　　　ｉ：　0　1　2　3　4　5　6　7　8　…
　　　ｔ：　-　-　a　b　c　a　b　x　?　…
　　　ｐ：　　　　a0 b1 c2 a3 b4 b5 c6
　　　　　　　　　　 　 　 　 　 └ここで不一致
ｐ[５] で不一致だということは、ｐ[０]～ｐ[４] はｔと一致していたことになります。 比較位置の一つ手前（６）のｐはｂ４、その前（５）はａ３です。すなわち、位置５～６にａ０とｂ１がくるように移動させる必要があります。→next[５]＝３
　　　ｉ：　0　1　2　3　4　5　6　7　8　…
　　　ｔ：　-　-　a　b　c　a　b　x　?　…
　　　ｐ：　　　　　　　　 a0 b1 c2 a3 b4 b5 c6
　　　　　　　　　　　 　 　 　 └ここから比較

ｂ４とｂ５の場合を一般化すると次のようになります。
　「ｔ[ｉ]≠ｐ[ｊ] になったとき、ｐをｋだけ右に移動するとします。
　ｊｊをｋからｊ－１まで変化させ、すべてのｊｊでｐ[ｊｊ]＝ｐ[ｊｊ－ｋ]になれば、そのｋがnext[ｊ]になります。
　もし、途中でｐ[ｊｊ]≠ｐ[ｊｊ－ｋ]になれば、ｋを１ふやして繰り返します。」
　ここで、ｐ[ｊｊ]とは、ある比較位置ｉｉでの移動前でのｐの文字であり、その位置でのｔ[ｉｉ]の文字でもあります。そして、ｐ[ｊｊ－ｋ]とは、ｐをｋだけ移動したときの、位置ｉｉに対応するｐの文字です。そのため、ｐ[ｊｊ]≠ｐ[ｊｊ－ｋ]になるならば、ｋ個の移動では、ｔとｐを比較するまでもなく不一致になります。それで、ｋを増加する（さらに右に移動させる）のです。

具体的に、ｂ５のときを考えましょう。ｉ＝７、ｊ＝５で、ｔ[７]（＝ｘ）≠ｐ[５] （＝ｂ５）になりました。 　ｋ＝１のとき（ｐを右に１つ移動させたとき）
　　ｊｊ＝１～４に変化させますが、
　　　ｊｊ＝１のとき、ｐ[ｊｊ]＝ｐ[１]＝ｂ１、ｐ[ｊｊ－ｋ]＝ｐ[０]＝ａ０で不一致
　　　　　これは、位置ｉｉ＝３で、ｔ[３]＝ｂなのに、ｐがａ０なので不一致だったという意味です。
　ｋ＝２のとき（ｐを右に２つ移動させたとき）
　　ｊｊ＝２～４に変化させますが、
　　　ｊｊ＝２のとき、ｐ[ｊｊ]＝ｐ[２]＝ｃ２、ｐ[ｊｊ－ｋ]＝ｐ[０]＝ａ０で不一致
　　　　　これは、位置ｉｉ＝４で、ｔ[４]＝ｃなのに、ｐがａ０なので不一致だったという意味です。
　ｋ＝３のとき（ｐを右に３つ移動させたとき）
　　ｊｊ＝２～４に変化させます。
　　　ｊｊ＝３のとき、ｐ[ｊｊ]＝ｐ[３]＝ａ３、ｐ[ｊｊ－ｋ]＝ｐ[０]＝ａ０で一致
　　　ｊｊ＝４のとき、ｐ[ｊｊ]＝ｐ[４]＝ｂ４、ｐ[ｊｊ－ｋ]＝ｐ[１]＝ｂ１で一致
　　　　　ｔ[５]＝ａ、ｔ[６]＝ｂが移動後のａ０とｂ１に一致しているという意味です。
　　　　　この後は、ｔ[６]＝？と移動後のｂ２を比較することになります。

●Ｃ６：
　　　ｉ：　0　1　2　3　4　5　6　7　8　9　…
　　　ｔ：　-　-　a　b　c　a　b　b　x　?　…
　　　ｐ：　　　　a0 b1 c2 a3 b4 b5 c6
　　　　　　　　　　 　 　 　 　 　 └ここで不一致
　ｃ６のときは、次のように６個移動させる必要があります。→next[６]＝６
　　　ｉ：　0　1　2　3　4　5　6　7　8　9　…
　　　ｔ：　-　-　a　b　c　a　b　b　x　?　…
　　　ｐ：　　　　　　　　　　　　　a0 b1 c2 a3 b4 b5 c6
　　　　　　　　　　 　 　 　 　 　 └ここから比較

　ｂ５のときの方法ですと、ｋ＝ｊ－１＝４まで行っても、ｐ[ｊｊ]≠ｐ[ｊｊ－ｋ]になってしまいます。それで、このような場合は、next[ｊ]＝ｊとなることがわかります。

以上をまとめると、next[ｊ] を計算する手順は次のようになります。

• ルール１：無条件で、next[０]＝１とする。
• ルール２：ｊ≧１ のとき、
  　　ｋを１からｊ－１まで繰り返す
  　　　　ｊｊをｋからｊ－１まで繰り返す
  　　　　　　すべてのｊｊで ｐ[ｊｊ]＝ｐ[ｊｊ－ｋ] ならば、 next[ｊ]＝ｋ
  　　　　｝
  　　｝
• ルール３：すべてのｋで ｐ[ｊｊ]≠ｐ[ｊｊ－ｋ] が発生したら、 next[ｊ]＝ｊ

トレース

プログラムの（ウ～サ）をトレースすると、次のようになります。

　　ｊ　ｋ ｊｊ　jj-k　p[jj]　p[jj-k]　next[j]　
　　０　　　　　　　　　　　　　　　　　１　ルール１
　　１　　　　　　　　　　　　　　　　　１　ルール３
　　２　１　１　　０　　ｂ　　　ａ　　　２　ルール３
　　３　１　１　　０　　ｂ　　　ａ
　　３　２　２　　０　　ｃ　　　ａ　　　３　ルール３
　　４　１　１　　０　　ｂ　　　ａ
　　４　２　２　　０　　ｃ　　　ａ
　　４　３　３　　０　　ａ　＝　ａ　　　３　ルール２
　　５　１　１　　０　　ｂ　　　ａ
　　５　２　２　　０　　ｃ　　　ａ
　　５　３　３　　０　　ａ　＝　ａ
　　５　３　４　　１　　ｂ　＝　ｂ　　　３　ルール２
　　６　１　１　　０　　ｂ　　　ａ
　　６　２　２　　０　　ｃ　　　ａ
　　６　３　３　　０　　ａ　＝　ａ
　　６　３　４　　１　　ｂ　＝　ｂ
　　６　３　５　　２　　ｂ　　　ｃ
　　６　４　４　　０　　ｂ　　　ａ
　　６　５　５　　０　　ｂ　　　ａ　　　６　ルール３

ＢＭ法（Boyer- Moore algorithm）

ＢＭ法は、ｐとｔを比較するのに、ｐの末尾から順に前へと比較することにより、一挙に大きくｐを右に移動させる工夫をしています。
　例えば、ｔとｐが下図の位置関係にあるとき、ｐの末尾ｂとｔのｘが不一致になったとします。
　　　　　　０１２３４５６７８９
　　　ｔ：　－－？？？ｘ？？？？
　　　ｐ：　　　ａｂｃｂ
　　　ア：　　　│ａｂｃｂ
　　　イ：　　　│　ａｂｃｂ
　　　ウ：　　　│　　ａｂｃｂ
　　　エ：　　　│　　　ａｂｃｂ
　　　　　　　　└───┘
　このとき、ｘがｐに存在しない文字であれば、ア～ウでは、いずれもｘと一致しないのですから、他のｔやｐを比較するまでもなく、エのように、ｐをｍ（ｐの文字数）だけ移動することができます。
　また、ｘがｐに存在する文字、例えばｃであれば、ｐの比較した個所から直前のｃのところが比較位置にくるように移動すればよいことになります。
　　　　　　０１２３４５６７８９
　　　ｔ：　－－？？？ｃ？？？？
　　　ｐ：　　　ａｂｃｂ
　　　ア：　　　　ａｂｃｂ
　このように、ｔの文字が、ｐに存在しない文字ならｍ、存在する文字なら、その文字に対応した移動量（例えばｃならば１のように）の表を作っておけば、比較して不一致になったときに、ｔの文字により、ｐを移動させることができます。下のプログラムでは、その表を skip としています。

プログラム

ア　function bm() {
イ　　　var i, j, k;
　　　/* skip[j] の設定 */
ウ　　　skip = new Array();
エ　　　skip["a"] = m; skip["b"] = m; … , skip["z"] = m;
オ　　　for (j=0; j<m; j++)　skip[p[j]] = m-j-1;
　　　/* ｔとｐの比較 */
カ　　　i = 0;
キ　　　while (i <= n-m) {
ク　　　　　j = m - 1;
ケ　　　　　while ((j >= 0) && (t[i+j] == p[j]) ) j--;
コ　　　　　if (j < 0) return i;
サ　　　　　k = skip[t[i+j]] - (m-j-1);
シ　　　　　if (k > 0) i = i + k;
ス　　　　　else i = i + 1;
セ　　　}
ソ　　　return -1;
タ　}

トレース

●ウ～オ：skip の設定
Javascriptでは（Ｃ言語も）、skip["ａ"] や skip["ＢＭ法"] のように、配列の添字を文字リテラルで与えることができます（詳細は文法書を参照してください）。
　エでは、ｔで出現するであろうすべての文字種について、値をｍに設定しておきます。これは、ｐに存在しない文字で不一致になったとき、ｐの文字数（ｍ＝４）だけ、ｐを右に移動させるためです。

オは、ｐに存在する文字についての設定です。
　オを実行すると次のようになります。
　　　ｊ　ｐ[ｊ]　skip[p[j]]
　　　０　　ａ　　skip["ａ"]＝３
　　　１　　ｂ　　skip["ｂ"]＝２　　①
　　　２　　ａ　　skip["ｃ"]＝１
　　　３　　ｂ　　skip["ｂ"]＝０　　②
①と②が重複しますが、後のもので上書きされるので、末尾のほうが優先され②が残り、skip["ｂ"]＝０となります。
　結果として、オが終了した段階では、skip の値は次のようになっています。
　　　ａのとき３
　　　ｂのとき０
　　　ｃのとき１
　　　その他のとき４

●キ～ス：ｔとｐの比較
ここではｔを次の文字列だとします。ｎ＝１２です。
　　　ｉ：　０１２３４５６７８９101112
　　　ｔ：　ｄｂｃｂｂｄｂａｂｃｂａ

ｉ＝０のとき
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄｂｃｂｂｄｂａｂｃｂａ
　　　ｐ：　ａｂｃｂ

• キで、ｉ＝０≦ｎ－ｍ＝８なので、ｊ＝ｍ－１＝３となり、ケに行きます。
• ケで、ｔ[i+j]＝ｔ[３]＝ｂ、ｐ[j]＝ｐ[３]＝ｂですので、ｔ[i+j]＝ｐ[j]となり、ｊ－－＝２（ｉ＋ｊ＝２）となり、ケが繰り返されます。
  ｊ＝２のとき：ｔ[i+j]＝ｔ[３]＝ｃ、ｐ[j]＝ｐ[２]＝ｃ　→ｔ[i+j]＝ｐ[j]　（一致）
  ｊ＝１のとき：ｔ[i+j]＝ｔ[２]＝ｂ、ｐ[j]＝ｐ[１]＝ｂ　→ｔ[i+j]＝ｐ[j]　（一致）
  ｊ＝０のとき：ｔ[i+j]＝ｔ[０]＝ｄ、ｐ[j]＝ｐ[０]＝ａ　→ｔ[i+j]＝ｐ[j]　（不一致）
  ｊ＝０、ｉ＋ｊ＝０のとき、コに行きます。【注１】
• コでは、ｊ＝０≧０なので、サへ行きます。
• サでは、skip[t[i+j]] ＝skip[t[０]]＝skip[ｄ]＝４、ｍ－ｊ－１＝４－０－１＝３なので、ｋ＝４－３＝１になります。【注２】
• シで、ｋ＞０なので、ｉ＝ｉ＋ｋ＝０＋１＝１となり、キへ戻ります。

【注１】

ケは、ｐを末尾から順にｔとｐを比較して、不一致となるｊ（およびｉ＋ｊ）を求める操作だといえます。
すべてのｐが一致したときには、ｊ＝－１になります。そのときのｐの先頭位置はｉですので、コで retun i として処理が終了します。
なお、ケでｊ≧０の条件を付けているのは、ｊ＝－１になっても、ｔ[i+j] と ｐ[j] の比較を行おうとして、ｐ[－１] となり配列要素をはみ出すのを防ぐためです。

【注２】

先に skip[t[i+j]] とは、ｔ[i+j]とｐ[j]が一致しなかったときに、ｔ[i+j]の文字種により、ｐを移動させる距離だといいました。それならば、サは　ｋ＝skip[t[i+j]]　でよいのではないかと考えられます。どうして、(ｍ－ｊ－１) を引く必要があるのでしょうか？

ここまでで比較した（文字がわかっている）のは、
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄｂｃｂ？？？？？？？？
　　　ｐ：　ａｂｃｂ
だけです（？の部分はわかっていない）。
　しかも、ＢＭ法（簡易ＢＭ法）では、先に比較した結果は忘れています【注３】ので、
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄ？？？？？？？？？？？
　　　ｐ：　ａ？？？
となります。
　ｋ＝skip[t[i+j]]（＝４） としたのでは、
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄ？？？？？？？？？？
　　　ｐ：　　　　　ａ？？？
になってしまいます。あるいはｔが、
　　　　　　０１２３４５６７８９1011
　　　ｔ：　？ａｂｃｄ？？？？？？
　　　ｐ：　　　　　ａｂｃｂ
となっていたら、一致しているのを見逃すことになります。
　これを回避するには、下図のように、ｍ－ｊ－１個だけ戻す必要があるのです。
　　　　　　０１２３４５６７８９1011
　　　ｔ：　？ａ？？？？？？？？？
　　　ｐ：　ａ？？？
　　ｊの値─┘　　　└─ｍの値
　　　　　　└─┬┘
　　　　　　　　m-j-1 = 4-0-1 = 3

【注３】

ここで紹介しているのは（簡易）ＢＭ法です。（拡張）ＢＭ法では、ＫＭＰ法のように、それまでに比較した結果を記録しておき、それを利用することにより、さらに効率的にｐを移動させることができます。

ｉ＝１のとき
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄｂｃｂｂｄｂａｂｃｂａ
　　　ｐ：　　ａｂｃｂ

i=1, j=3, t[i+j]=b, p[j]=b 　　j=j-1=2, t[i+j]=b, p[j]=c i+j=3, t[i+j]=b, skip=0, m-j-1=1, k=-1 i=i+1=2

• キで、ｉ＝１≦ｎ－ｍ＝８なので、ｊ＝ｍ－１＝３となり、ケに行きます。
• ケで、ｔ[i+j]≠ｐ[j]となるのは、ｔ[３]＝ｂ、ｐ[２]＝ｃのときですので、ｊ＝２、ｉ＋ｊ＝３でコに行き、さらにサに行きます。
• サでは、skip[t[i+j]] ＝skip[t[３]]＝skip[ｂ]＝０、ｍ－ｊ－１＝４－２－１＝１なので、ｋ＝０－１＝－１になります。
• シで、ｋ≦０なのでスに行きます。【注４】
• スで、ｉ＝ｉ＋１＝２となり、キに戻ります。

【注４】

どうして、シではなく、スにするのでしょうか？
　ｉ＝１のときは、次のようになっていました。
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄｂｃｂｂｄｂａｂｃｂａ
　　　ｐ：　　ａｂｃｂ

シを採用すると、ｋが負なので、ｉ＝ｉ＋ｋ＝１－１＝０になり、
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄｂｃｂｂｄｂａｂｃｂａ
　　　ｐ：　ａｂｃｂ

のように、左に戻ってしまいます。これで一致するはずがありません。

ｉ＝２のとき
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄｂｃｂｂｄｂａｂｃｂａ
　　　ｐ：　　　ａｂｃｂ

• ケで、ｊ＝３、ｉ＋ｊ＝５のときにｄ≠ｂとなり、そのままコに行き、さらにサに行きます。
• サでは、skip[t[i+j]] ＝skip[t[５]]＝skip[ｄ]＝４、ｍ－ｊ－１＝４－３－１＝０なので、ｋ＝４になります。
• シで、ｋ＞０なので、ｉ＝ｉ＋ｋ＝２＋４＝６となり、キへ戻ります。【注４】

【注４】

この結果、ｐを大きく移動できました。特にｔの文字がｐにないとき、大きな（ｍ個）移動ができるのが、ＢＭ法の特徴です。
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄｂｃｂｂｄｂａｂｃｂａ
　　　ｐ：　　　　　　　ａｂｃｂ

ｉ＝６のとき

• ケで、ｊ＝３、ｉ＋ｊ＝９のときにｃ≠ｂとなり、そのままコに行き、さらにサに行きます。
• サでは、skip[t[i+j]] ＝skip[t[９]]＝skip[ｃ]＝１、ｍ－ｊ－１＝４－３－１＝０なので、ｋ＝１になります。
• シで、ｋ＞０なので、ｉ＝ｉ＋ｋ＝６＋１＝７となり、キへ戻ります。

ｉ＝７のとき
　ｐの位置は、下のようになっています。
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄｂｃｂｂｄｂａｂｃｂａ
　　　ｐ：　　　　　　　　ａｂｃｂ

• キでは、ｉ＝７≦ｎ－ｍ＝１２－４＝８ですので、クに行きます。【注５】
• ケにおいて、すべてのｐが一致したので、ｊ＝－１になり、コに行きます。
• コでは、ｊ＝－１＜０なので、ｉ＝７として処理が終了します。

【注５】

探索範囲を ｉ≦ｎ－ｍ としているのは、下図から明白でしょう。ｉ＝ｎ－ｍになっても一致しなかったとき（コでｋ≦０であったとき）は、ソに行き、不一致を示す－１となり処理を終了します。
　　　　　　　　　　　　　ｎ－ｍ　　ｉ
　　　　　　　　　　　　　　↓　　　↓
　　　　　　０１２３４５６７８９1011
　　　ｔ：　ｄｂｃｂｂｄｂａｂｃｂａ
　　　ｐ：　　　　　　　　　ａｂｃｂ
　　　　　　　　　　　　　　０１２３
　　　　　　　　　　　　　　　　　　↑
　　　　　　　　　　　　　　　　　　ｍ

計算プログラム