シフタアルゴリズム
Shifter algorithm
長さmの文字列検索のマッチ状態をmビットで表現
Matching status represented in m-bit value
k文字マッチをk番目のビットで表現
e.g.
11101
= 2文字マッチ
次の文字がcであるとき、この状態変数を1ビット左にシフトし、T[c]とのORを計算することにより新しい状態を計算
T[c]はあらかじめ計算しておく値で、パタン文字==cの位置だけ0になっている。
e.g. パタン
abac
→ T['a']=
0101
ミスマッチを許すときはORのかわりに加算を使用