バグの発生しない文字列検索の書き方

検索される文字列をs、検索する文字列をtとおいたとき、次のようにループを書けばバグは発生しない。

for (int i = 0; i + t.size() <= s.size(); i++) {
  if (s.substr(i, t.size()) == t) {
    /*  */
  }
}

ポイントは半開区間[l, r)で考えること。
|S| = S.size()とすると、sの参照可能な区間は[0, |s|)であり、sのi文字目から|t|文字を参照するので参照したい範囲は[i, i + |t|)。つまり、[0, |s|)が[i, i + |t|)を包含しなければならないので、以下の条件式を満たす必要がある。

1. i >= 0
2. i + |t| <= |s|

iの定義により1.は必ず満たすので、2.のみをループの継続条件にすればいい。

substr()の性質から、わざわざ上のように書く必要はない。しかし、上の書き方は通常の配列にも対応できる。

for (int i = 0; i + t.size() <= s.size(); i++) {
  bool match = true;
  for (int j = 0; j < t.size(); j++) {
    if (t[j] != s[i + j]) match = false;
  }
  if (match) {
    /*  */
  }
}

substr()の性質を利用したコードをそのまま配列に流用すると、配列外参照が発生する可能性がある（|t| = 1のときだけ発生しない）。

// OK
for (int i = 0; i < s.size(); i++) {
  if (s.substr(i, t.size()) == t) { }
}

// NG
for (int i = 0; i < s.size(); i++) {
  bool match = true;
  for (int j = 0; j < t.size(); j++) {
    if (t[j] != s[i + j]) match = false;
  }
  if (match) { }
}