1498. КМП

Найдите все вхождения строки word в строку text.

Вход. Первая строка содержит строку text, вторая строка содержит строку word. Длины обеих строк больше 0 и меньше 50000. Строки состоят только из латинских букв.

Выход. Выведите номера символов, начиная с которых строка word входит в строку text, в порядке возрастания. Как это принято в программировании, индексация символов начинается с нуля.

Пример входа	Пример выхода
ababbababa aba	0 5 7

РЕШЕНИЕ

строки – Кнут-Моррис-Пратт

Анализ алгоритма

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

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

Объявим следующие переменные:

· 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;