よくわかるKMP - ペリャウドの日

vector<int> Build(const string& s) {
  vector<int> fail(s.size() + 1);

  int j = -1;
  fail[0] = -1;
  for (int i = 0; i < s.size(); ++i) {
    while (j >= 0 && s[i] != s[j]) j = fail[j];
    ++j;
    fail[i + 1] = j;
  }
  return fail;
}

void Match(const string& needle,
           const string& haystack,
           vector<int> *matches) {
  const vector<int> fail = Build(needle);
  matches->clear();

  int j_needle = 0;
  for (int i_haystack = 0; i_haystack < haystack.size(); ++i_haystack) {
    while (j_needle >= 0 && needle[j_needle] != haystack[i_haystack])
      j_needle = fail[j_needle];
    ++j_needle;
    if (j_needle >= needle.size()) {
      matches->push_back(i_haystack - j_needle + 1);
      j_needle = fail[j_needle];
    }
  }
}

fail配列というのを作るのがミソ。
fail配列というのは、その時点までで入力された文字列(のsuffix)と、needleのprefixが何文字一致するかというオートマトン（pattern matching automaton）を配列の形で表現したものである。

つまり1. two pointersっぽいアルゴリズムでfail配列を構築するBuildと、と 2. それを使って効率的にneedleのポインタを移動させつつhaystackとのマッチングを行うMatchからKMPのアルゴリズムは成る。

1.のBuildについてはneedleの任意地点についてneedle自身の先頭とのマッチングを線形に取っているという風にも見ることができる。したがって、例えば文字列の周期をneedle.size() - fail.back()で取るなどの用途にも使える（例: needle = "abcabc" => needle.size() - fail.back() = 3 なぜならば"abc" x 2）。