カテゴリー:
探索アルゴリズム
閲覧数:353 配信日:2018-03-14 08:23
前提
検索文字列パターン
なるべくなる
border
・「単語の2文字目で不一致となった場合のバックトラックする文字数」で構成された配列
※配列名は任意だが、慣用的にborderを使用することが多い
比較再開テーブルを作成
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 検索文字列パターン | な | る | べ | く | な | る |
比較再開テーブル0
border[0]を-1 とする
・パターン最初の部分での不一致は特別なケース（バックトラッキングの可能性はない）ので、 border[0] = -1を設定
※文字内容に関わらず常に固定値-1
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 検索文字列パターン | な | る | べ | く | な | る |
| border | -1 | . | . | . | . | . |
比較再開テーブル1
border[1]を0 とする
・単語の2文字目で不一致となった場合のバックトラックする文字数であるが、(仮に一致した状態であったとしても)1文字しか一致していない状態ではバックトラックできないため
※文字内容に関わらず常に固定値0
計算式に無理やり当てはめてみる
・検索文字列パターン[0] から 検索文字列パターン[1-1] までの文字列について、検索文字列パターン[1-1] で終わる文字列と 検索文字列パターン[0] から始まる文字列が一致するかどうかを調べる
・「な」から「な」までの文字列について、「な」 と 「な」 が一致するかどうかを調べる
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 検索文字列パターン | な | る | べ | く | な | る |
| border | -1 | 0 | . | . | . | . |
比較再開テーブル2
border[2]を0 とする
・検索文字列パターン[0] から 検索文字列パターン[2-1] までの文字列について、検索文字列パターン[2-1] で終わる文字列と 検索文字列パターン[0] から始まる文字列が一致するかどうかを調べる
・「な」から「る」までの文字列について、「る」 と 「な」 が一致するかどうかを調べる
・一致していないので「0」
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 検索文字列パターン | な | る | べ | く | な | る |
| border | -1 | 0 | 0 | . | . | . |