Z и префикс функции

Z-функция и префикс-функция — это два различных инструмента, используемых для анализа строк, и они имеют разные определения и применения. Вот основные различия между ними:

Определение

1. Префикс-функция:

   • Префикс-функция для строки $S$ длины $n$ определяется массивом $p$ длины $n$.
   • Значение $p[i]$ указывает длину наибольшего собственного префикса строки $S[0:i]$, который также является суффиксом этой строки.

2. Z-функция:

   • Z-функция для строки $S$ длины $n$ определяется массивом $Z$ длины $n$.
   • Значение $Z[i]$ обозначает длину наибольшей подстроки, начинающейся с позиции $i$, которая также является префиксом строки $S$.

Пример

Рассмотрим строку S = "абабаба".

1. Префикс-функция:

   • $p[0]=0$ (первый символ не имеет префикса).
   • $p[1]=0$ (“а” не совпадает с “б”).
   • $p[2]=1$ (“аб” имеет префикс “а”, который совпадает с первым символом).
   • $p[3]=2$ (“аба” имеет префикс “аб”, который совпадает с первыми двумя символами).
   • $p[4]=3$ (“абаб” имеет префикс “аба”, который совпадает с первыми тремя символами).
   • $p[5]=4$ (“абаба” имеет префикс “абаб”, который совпадает с первыми четырьмя символами).
   • $p[6]=5$ (“абабаб” имеет префикс “абаба”, который совпадает с первыми пятью символами).

   Префикс-функция: $[0,0,1,2,3,4,5]$.

2. Z-функция:

   • $Z[0]=7$ (вся строка совпадает с собой).
   • $Z[1]=0$ (подстрока, начинающаяся с “бабаба”, не совпадает с началом строки).
   • $Z[2]=5$ (“абаба” совпадает с началом строки “абаба”).
   • $Z[3]=0$ (подстрока, начинающаяся с “баба”, не совпадает с началом строки).
   • $Z[4]=3$ (“аба” совпадает с началом строки “аба”).
   • $Z[5]=0$ (подстрока, начинающаяся с “ба”, не совпадает с началом строки).
   • $Z[6]=1$ (“а” совпадает с началом строки “а”).

   Z-функция: $[7,0,5,0,3,0,1]$.

Различия в применении

1. Префикс-функция:

   • Используется в алгоритме Кнута-Морриса-Пратта (КМП) для поиска подстрок.
   • Помогает найти периодичность строки.
   • Применяется для анализа строк и других задач, связанных с префиксами и суффиксами.

2. Z-функция:

   • Используется в алгоритмах поиска подстрок, таких как алгоритм поиска по шаблону с использованием Z-функции.
   • Полезна для задач, связанных с нахождением совпадающих подстрок, и анализа повторяющихся паттернов.

Итог

Префикс-функция и Z-функция имеют разные определения и приложения, но обе они полезны для различных задач, связанных с анализом строк. Префикс-функция фокусируется на префиксах, которые также являются суффиксами, тогда как Z-функция измеряет совпадение префиксов с подстроками, начинающимися с каждой позиции строки.