Даны две строки, s и p. Сколько раз p встречается в s как подстрока? Важное дополнение: строка s — не простая, а циклическая. Циклическую строку можно представить себе так: запишем её на бумажной ленте, после чего склеим концы ленты так, чтобы после последней буквы s следовала первая её буква. Пусть s — циклическая строка из n букв, а p — обычная строка из k букв. Определим формально, сколько раз p встречается в s. Для каждого i = 1; 2; : : : ; n начнём с i-й буквы строки s и прочитаем ровно k б

Для решения этой задачи можно использовать алгоритм Кнута-Морриса-Пратта (алгоритм КМП).

Шаги решения на русском языке:

1. Создать вспомогательный массив lps (longest proper prefix which is also suffix), который будет содержать значения для каждого индекса в строке p.
2. Заполнить массив lps, используя алгоритм КМП.
– Установить начальные значения lps[0] = 0 и len = 0.
– Итерироваться по символам строки p, начиная со второго (индекс 1):
– Если текущий символ равен символу, следующему за последним символом префикса, то увеличить len на 1 и присвоить его значение lps[i].
– Если текущий символ не равен символу, следующему за последним символом префикса, то:
– Если len не равен 0, установить len равным значению lps[len-1] и продолжить сравнение текущего символа с символом, следующим за последним символом префикса.
– Если len равен 0, установить lps[i] равным 0 и перейти к следующему символу.
– Вернуть массив lps.
3. Используя алгоритм КМП, найти количество раз, которое строка p встречается в строке s.
– Установить начальные значения count = 0 и i = 0.
– Итерироваться по символам строки s:
– Если текущий символ равен символу строки p, двигаться по обоим строкам вперед.
– Если i равно длине строки p, значит, найдено вхождение строки p. Увеличить count на 1.
– В противном случае, переместить указатель в строке p, используя lps[i].
– Если текущий символ не равен символу строки p, переместить указатель в строке p, используя lps[i-1], и продолжить сравнение символов с символом строки p.
– Вернуть значение count.

Алгоритм КМП позволяет эффективно находить все вхождения строки p в циклической строке s, используя O(n) времени и O(k) дополнительной памяти, где n – длина строки s, k – длина строки p.