■

文字列解析のBM法で、文字をスキップするためのテーブルに入れる値を
考えていた時に、iをx軸上において考えれば楽なんじゃないかと思って
思考してみた

検索される文字列をtextとし、探索する文字列をpatternと呼ぶ。
textの文字配置位置をX軸上の整数値と合わせ、現在注目している
点を原点Oとする。
patternは最初に原点Oに置き、注目点をx軸マイナス方向に1ずつ
動かし、textとpatternの配置文字列が一致するかを調べる。

そこで、一致しなかった点をとし、text[  ]
と同じ値を持つpattern上の文字で一番右端の点をとする。
BM法では、patternをずらしをの位置まで
持ってくる事を要求しているのでpatternの右端は原点Oから

だけ動かせば良い。
これは現在注目している点からすると


だけ動かせばよい事になる。
これはすなわちpattern配列上の右端からこの文字がある位置までの距離
なので pattern_length - 1 - i (iは左端を0とした、左端からの位置）
となる。

文字で書くとややこしいけど、数直線書いてみると結構しっくり来た。
これはi,jの場合にはx,y軸考えてみれば結構楽に思考出来るんじゃないか！
と思ったけど、、そうでもなさそう。。orz