КМП (Розбір)

У задачі необхідно реалізувати алгоритм Кнута-Морріса-Пратта пошуку в тексті підрядка.

Реалізація алгоритму

Оголосимо наступні змінні:

• $text$ — рядок, в якому потрібно знайти всі входження шаблону $word$.

• $word$ — підрядок (шаблон), який ми шукаємо в рядку $text$.

• $p$ — префікс-функція для рядка $word$.

• $pos$ — список всіх позицій в рядку $text$, з яких починається входження підрядка $word$.

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

Функція MaxBorderArray обчислює префікс-функцію рядка $s$ і зберігає її значення в масиві $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;
  }
}

Функція kmp реалізує алгоритм Кнута — Морріса — Пратта. Всі індекси початку входжень рядка $word$ в текст $text$ зберігаються в масиві $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++;

Якщо індекс $j$ досяг останнього символу рядка $word$, це означає, що в тексті знайдено повне входження слова $word$. Початкова позиція знайденого входження дорівнює i - j + 1 (нумерація символів починається з нуля).

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

Основна частина програми. Читаємо вхідні рядки.

cin >> text;
cin >> word;

Запускаємо алгоритм Кнута-Морріса-Пратта.

kmp(word, text);

Виводимо знайдені позиції входження.

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