考え方例1

「プログラミング」及び「開発」関連用語集

カテゴリー: 探索アルゴリズム  閲覧数:359 配信日:2016-11-09 08:58


例1


6文字パターンREDRED」を探索


1文字目が不一致


スタート
テキスト
パターン R E D R E D
1文字目が不一致の場合
・「テキスト」位置情報を1つ進める
・「パターン」を1つ右へずらす
・「パターン」先頭から比較
テキスト
パターン - R E D R E D


2文字目が不一致


スタート
・この時点では「デキスト」と「パターン」の1文字目が一致している
テキスト R
パターン R E D R E D
2文字目が不一致の場合
・「パターン」を1つ右へずらす
・「パターン」先頭から比較
※「テキスト」を指すポインタ位置は 変わらないことに注意
テキスト R
パターン - R E D R E D


3文字目が不一致


スタート
・この時点では「デキスト」と「パターン」の1〜2文字目が一致している
テキスト R E
パターン R E D R E D
3文字目が不一致の場合
・「パターン」を2つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」先頭から比較
テキスト R E
パターン - - R E D R E D


4文字目が不一致


スタート
・この時点では「デキスト」と「パターン」の1〜3文字目が一致している
テキスト R E D
パターン R E D R E D
4文字目が不一致の場合
・「パターン」を3つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」先頭から比較
テキスト R E D
パターン - - - R E D R E D


5文字目が不一致


スタート
・この時点では「テキスト」と「パターン」の1〜4文字目が一致している
・テキストの1文字目と4文字目は同じ文字Rになっている
テキスト R E D R
パターン R E D R E D
パターンを4つずらすと?
・テキスト4文字目のRを 見逃してしまう
テキスト R E D R
パターン - - - - R E D R E
5文字目が不一致の場合
・「パターン」を3つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」2文字目から比較を続行
テキスト R E D R
パターン - - - R E D R E D


6文字目が不一致


スタート
・この時点では「デキスト」と「パターン」の1〜5文字目が一致している
テキスト R E D R E
パターン R E D R E D
6文字目が不一致の場合
・「パターン」を3つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」3文字目から比較
テキスト R E D R E
パターン - - - R E D R E D



考え方


パターンの i 文字目で失敗した
・0 から i - 1 文字はテキストとパターンが一致している 

ポイント
・パターンの i 文字目で失敗した時に、何文字ずらして再開するか

例1の場合
・1文字目で失敗 => ずらし数 next[0] = 1
・2文字目で失敗 => ずらし数 next[1] = 1
・3文字目で失敗 => ずらし数 next[2] = 2
・4文字目で失敗 => ずらし数 next[3] = 3
・5文字目で失敗 => ずらし数 next[4] = 3
・6文字目で失敗 => ずらし数 next[5] = 3


計算量
・O(n)



文字列検索(直感的な文字列検索とKMP法)