String: KMP Pattern Search

One correct implementation. Alternative approaches that satisfy the constraints are equally valid — the reviewer judges behaviour, not style.

#include <bits/stdc++.h>
using namespace std;

vector<int> buildLPS(const string& p) {
  vector<int> lps(p.size(), 0);
  for (int i = 1, len = 0; i < (int)p.size(); ) {
    if (p[i] == p[len]) lps[i++] = ++len;
    else if (len) len = lps[len - 1];
    else lps[i++] = 0;
  }
  return lps;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string text, pat; cin >> text >> pat;
  vector<int> lps = buildLPS(pat);
  vector<int> pos;
  for (int i = 0, j = 0; i < (int)text.size(); ) {
    if (text[i] == pat[j]) { i++; j++; if (j == (int)pat.size()) { pos.push_back(i - j); j = lps[j - 1]; } }
    else if (j) j = lps[j - 1]; else i++;
  }
  if (pos.empty()) cout << -1;
  else {
    for (int i = 0; i < (int)pos.size(); i++) {
      if (i) cout << ' ';
      cout << pos[i];
    }
  }
  cout << '\n';
  return 0;
}