Где применяется
1. Задача
С какой позиции в «hello world» начинается «world»? Сколько раз «ab» встречается в «ababab»? Эти вопросы решает каждое нажатие Ctrl-F, каждый запуск grep, каждая проверка «есть ли в этой строке лога слово ERROR». В языках для этого есть готовые indexOf, strstr или in. Здесь ты напишешь поиск сам. Простая версия учит сравнивать символы, сдвигая образец по тексту, и этот приём потом встречается во многих строковых задачах. А когда знаешь, сколько стоит простая версия, понятно, когда нужен алгоритм быстрее.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где короткий образец ищут в тексте или проверяют, входит ли одна строка в другую. Перебор каждого старта со сравнением по буквам стоит O(n * m) и проходит, когда строки короткие.
Это findSubstring из урока. Обе строки не длиннее 10^4, так что простой поиск проходит.
Слов не больше 100 и в каждом не больше 30 букв, так что проверь каждую пару поиском из урока.
s собрана из одного повторённого куска ровно тогда, когда s находится внутри s + s без первой и последней буквы.
Повторяй a, пока она не станет не короче b, попробуй ещё одну копию и ищи b в каждой.