Z-функция для поиска шаблона
Сопоставляйте префиксы по всей строке
«Z-функция для поиска шаблона» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Ещё один инструмент для поиска совпадений
Z-функция — удобная альтернатива KMP для поиска шаблона. Многие считают, что с ней проще рассуждать. ✨
Что означает z[i]
Для каждого индекса z[i] — это длина самой длинной подстроки, начинающейся в позиции i и совпадающей с префиксом всей строки.
Небольшой пример
Для aabaab массив z имеет вид 0,1,0,3,1,0. В позиции 3 фрагмент aab совпадает с префиксом, поэтому его длина равна 3.
Z-блок
Мы отслеживаем окно [l, r] — самое правое найденное совпадение. Это позволяет повторно использовать результаты предыдущих сравнений.
l, r = 0, 0Внутри блока
Когда i находится внутри блока, Вы копируете известное значение z в качестве начального значения, ограничивая его границей блока.
if i < r:
z[i] = min(r - i, z[i - l])Выход за границу блока
После начального значения Вы продолжаете сравнивать символы по одному, пока они совпадают с префиксом.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1Сдвигаем блок вперёд
Если совпадение простирается правее, обновите l и r, чтобы будущие индексы могли его повторно использовать.
if i + z[i] > r:
l, r = i, i + z[i]Гарантия линейного времени
Блок движется только вправо, поэтому общий объём работы равен O(n). Каждый символ обрабатывается ограниченное число раз.
Поиск с помощью Z-функции
Объедините pattern + sep + text и вычислите Z-функцию. Любое значение z, равное длине шаблона, означает найденное совпадение.
combined = pattern + chr(0) + text
z = z_function(combined)Считываем найденные совпадения
Просмотрите Z-массив: там, где выполняется z[i] == len(pattern), совпадение начинается в соответствующей позиции текста.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z-функция и KMP
Z-функция и KMP работают за линейное время. Z-функцию часто проще запрограммировать, поэтому это отличная запасная техника.
Быстрая проверка
Убедитесь, что Вы хорошо поняли смысл Z-массива.
Итоги: преимущества Z-функции
Вы построили Z-массив с помощью скользящего блока, выполнили поиск за линейное время и получили удобную альтернативу KMP. 🎯
Часто задаваемые вопросы
Урок «Z-функция для поиска шаблона» бесплатный?
Да — полный текст урока «Z-функция для поиска шаблона» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Z-функция для поиска шаблона»?
Сопоставляйте префиксы по всей строке Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Z-функция для поиска шаблона»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Префиксная функция KMP
- Полиномиальное хеширование строк
- Z-функция для поиска шаблона
- Деревья поиска по префиксам