Функция префикса используется во многих строковых алгоритмах, включая алгоритм Кнута-Морриса-Пратта для сопоставления строк. В этой статье выводится, реализуется и анализируется алгоритм, который вычисляет префиксную функцию заданной строки за линейное время.

Обозначения, терминология

В этой статье я буду использовать следующие обозначения и терминологию:

  • Если не указано иное, заглавные буквы относятся к строкам, а их строчная версия - к их длине (например, S - это строка длины s).
  • Индекс S - это целое число от 1 до s включительно.
  • TU обозначает строку, полученную путем объединения T и U, где T и U могут быть строками или символами.
  • Для всех индексов i, j из T, T [i] обозначает i -й символ T и T [i .. j] обозначает строку T [i]… T [j].

Границы и функция префикса

Мы рассматриваем строку S. Затем мы можем определить границы следующим образом:

Определение:

Граница S - это строка B, которая является собственным префиксом и собственным суффиксом S.

Например, пустая строка ε является границей любой непустой строки, но ε не имеет границ (потому что ее единственная подстрока - это сама, а не правильный префикс или суффикс). Самая длинная граница строки baobaba - ba.

Определение:

Префиксная функция S - это функция 𝜋, которая отображает индексы i S в длину самой длинной границы S [1 .. i].

Например, если мы рассмотрим строку baobaba, то 𝜋 (1) = 𝜋 (2) = 𝜋 (3) = 0, 𝜋 (4) = 1, 𝜋 (5) = 2, 𝜋 (6) = 1 и 𝜋 (7 ) = 2.

Наша цель - написать алгоритм, который берет строку и дает ее префиксную функцию.

Прокладывая путь

Первое интересное свойство границ говорит нам, что каждая граница S является самой длинной границей подстроки S. Точнее:

Свойство 1:

N-я самая длинная граница S является самой длинной границей (n-1) -й самой длинной границы S.

Доказательство чего-то в этом роде:

Схема доказательства:

Мы можем начать с доказательства того, что если A и B являются границами S, то из a ‹b следует, что A является границей B. В частности, n-я самая длинная граница S является границей (n-1) - тыс. Теперь нам нужно доказать, что он самый длинный. Предположим, что это не так: (n-1) -я по длине граница S имеет границу B, которая строго длиннее, чем n-я самая длинная граница S. Поскольку B является границей границы S, она должна быть граница S. Он строго короче (n-1) -й по длине и строго длиннее n-й по длине: это невозможно.

Мы будем использовать это свойство, чтобы вывести рекуррентное соотношение, чтобы найти все значения 𝜋.

Базовый случай прост: самая длинная граница строки, содержащей один единственный символ, - это ε. Следовательно, 𝜋 (1) = 0.

Предположим, что S имеет длину s ≥ 2. B - непустая граница S тогда и только тогда, когда все следующие условия выполнены:

  1. B[b] = S[s];
  2. B[1 .. b - 1] = S[s - b .. s - 1];
  3. B[b] = S[b];
  4. B[1 .. b - 1] = S[1 .. b - 1];
  5. b ≤ s - 1.

Мы только что перефразировали определение таким образом, чтобы последний символ границы отделялся от остальных. Утверждения 1. и 2. эквивалентны утверждению, что B является суффиксом S, утверждения 3. и 4. эквивалентны утверждению, что B является префиксом S, а утверждение 5. подразумевает, что B является правильным префиксом / суффиксом S. Это позволяет найти связь между границами S и границами S [1 .. s - 1]:

B является непустой границей S тогда и только тогда, когда: B [1 .. b - 1] является границей S [1 .. s - 1] и B [b] = S [b] = S [s ].

Это означает, что любая граница S создается путем добавления S [s] к границе S [1 .. s - 1] при условии, что S [s] = S [b ]. Следовательно:

Свойство 2:

S имеет непустую границу длины b тогда и только тогда, когда: S [1 .. s - 1] имеет границу длины b - 1 и S [b] = S [s].

Написание решения

Таким образом, мы можем установить следующий неформальный алгоритм:

Чтобы найти 𝜋 (i), переберите все длины границ b из S [1 .. i - 1] в порядке убывания. В первый раз S [b + 1] = S [i], мы полагаем 𝜋 (i) = b + 1. Если этого никогда не произойдет, 𝜋 (i) = 0.

Итак, мы начинаем с самой длинной границы S [1 .. i -1], длиной 𝜋 (i -1). Если S [𝜋 (i - 1) + 1] = S [i], мы можем установить 𝜋 (i) = 𝜋 ( i -1) + 1. В противном случае нам нужно найти длину второй самой длинной границы S [1 .. i -1]. Свойство 1 говорит нам, что оно задается как 𝜋 (𝜋 (i - 1)): вторая самая длинная граница S - самая длинная граница самой длинной границы S. Итак, нам нужно проверить, если S [1 .. 𝜋 (𝜋 (i - 1)) + 1] = S [i], в этом случае мы полагаем 𝜋 (i) = 𝜋 (𝜋 (i - 1)) + 1. Мы повторяем, пока не найдем самую длинную границу - если мы не находим ее, мы устанавливаем 𝜋 (i) = 0.

Это дает следующий алгоритм в псевдокоде (индексы массива и строки начинаются с 1):

Мы начинаем с инициализации массива, который соответствует префиксной функции (строка 4), и устанавливаем его первое значение равным 0 (это базовый случай).

Цикл while (строка 10) выполняет итерацию по всем длинам границ S в порядке убывания. Мы следим за тем, чтобы borderLength оставалось положительным (𝜋 (0) не имело бы никакого смысла). Если (borderLength + 1) -й символ строки равен i -го, то мы нашли нашу самую длинную границу (она имеет длину borderLength + 1).

Если строка условия 13 удовлетворяется, то мы нашли длину самой длинной границы S [1 .. i] и соответственно установили значение borderLength. В противном случае borderLength равно нулю, что соответствует максимальной длине границы S [1 .. i].

Поэтому мы можем определить 𝜋 (i) и двигаться дальше.

Анализ

Как и было обещано, алгоритм выполняется за Θ (с) времени в зависимости от длины строки. Это не очевидно, в частности из-за цикла while.

Единственная переменная, определяющая количество итераций цикла while, - borderLength. Он инициализируется значением 0 и может увеличиваться (строка 14) или уменьшаться (строка 11).

Поскольку borderLength всегда неотрицательно, он не может больше уменьшаться, чем увеличиваться. Он увеличивается не более чем на s - 1 (один раз за итерацию цикла for), что доказывает, что цикл while выполняется не более чем s - 1 раз за время выполнения. программы.

Поскольку цикл for выполняется ровно s - 1 раз, общая сложность compute-𝜋 составляет Θ (s).

Поддержите меня!

Спасибо за прочтение! Если вы нашли эту статью полезной, подумайте о том, чтобы подписаться на меня, чтобы помочь мне достичь порога в 100 подписчиков, необходимого для участия в программе Medium Partner Program. Это бесплатно и действительно помогает.

Вы также можете использовать мою реферальную ссылку для подписки на Medium: Стать участником. Вы получите доступ ко всем статьям на Medium, предназначенным только для участников, и ваш членский взнос будет напрямую поддерживать меня.

🐉