Поиск всех вхождений образца (КМП)
Строки
Средняя
Даны строки text и pattern. Найдите все начальные индексы вхождений pattern в text (вхождения могут пересекаться).
Наивная проверка каждой позиции целиком - O(n*m), не уложится на большом тесте. Используйте алгоритм Кнута-Морриса-Пратта.
Сигнатура функции
kmp_find_all(text: str, pattern: str) -> list[int]
Примеры
| Вход | Ожидаемый результат |
|---|
| ["ababcababc", "abc"] | [2, 7] |
| ["aaaa", "aa"] | [0, 1, 2] |
1решили
1пытались
100%успешность
Войдите, чтобы решить →