
文字列の一致判定を添字で追う
解き方
文字列中の短いパターンを探すときは、候補の開始位置とパターン内の位置を分けて追います。ここでは文字の位置を1から数えます。
手順を追う例
本文Tが「ABABA」、パターンPが「ABA」のとき、長さはそれぞれ5と3です。開始位置sは1から3まで試せます。パターンのj文字目を照合する本文の位置はs+j−1です。
確認問題【オリジナル】
s=2、j=2のときに比べる本文の位置と文字を答えてください。また全ての一致開始位置を答えてください。
答えと解説
本文の位置は2+2−1=3で、文字はAです。パターンの2文字目Bとは一致しません。開始位置1と3では3文字とも一致するため、答えは1と3です。重なった一致も数える設定では、1で見つかった後もsを1ずつ進めます。