KMP (Editorial)

This task requires implementing the Knuth–Morris–Pratt algorithm for substring search in a text.

Algorithm implementation

Define the following variables:

• $text$ — the string in which we need to find all occurrences of the pattern $word$.

• $word$ — the substring (pattern) we are searching for in the string $text$.

• $p$ — the prefix function array for the string $word$.

• $pos$ — a list of all positions in $text$ where occurrences of the substring $word$ begin.

string text, word;
vector<int> p, pos;

The function MaxBorderArray computes the prefix function of the string $s$ and stores its values in the array $p$.

void MaxBorderArray(string &s)
{
  p.resize(s.size());
  for (int i = 1; i < s.size(); i++)
  {
    int j = p[i - 1];
    while ((j > 0) && (s[i] != s[j])) j = p[j - 1];
    if (s[i] == s[j]) j++;
    p[i] = j;
  }
}

The function kmp implements the Knuth–Morris–Pratt algorithm. All starting indices of occurrences of the string $word$ in the text $text$ are stored in the array $pos$.

void kmp(string &word, string &text)
{
  MaxBorderArray(word);
  for (int i = 0, j = 0; i < text.size(); i++)
  {
    while (j && (text[i] != word[j])) j = p[j - 1];
    if (text[i] == word[j]) j++;

If the index $j$ reaches the last character of the string $word$, it means a complete occurrence of the word $word$ has been found in the text. The starting position of this occurrence is i - j + 1 (character indexing starts from zero).

    if (j == word.size()) pos.push_back(i - j + 1);
  }
}

The main part of the program. Read the input strings.

cin >> text;
cin >> word;

Run the Knuth-Morris-Pratt algorithm.

kmp(word, text);

Print the found occurrence positions.

for (auto x : pos)
  cout << x << " ";
cout << endl;