Префикс функция

Термины   15 января 2013  Автор статьи:  
geekbrains.ru/

Префикс функция — это такая функция от строки, которая для каждого элемента строки с номером i показывает наибольшую длину собственного суффикса подстроки с 0 до i элемента включительно, совпадающий с ее префиксом. Префикс — это подстрока начинающиеся с начала строки. Суффикс — это подстрока, заканчивающиеся в конце строки. Собственный — это значит не совпадающий со всей строкой. Таким образом для строки abc:

  • ab — собственный префикс
  • bc — собственный суффикс
  • abc — суффикс и префикс

Из — за того, что мы требуем, чтобы суффикс был собственным, полагаем префикс функция от 0 равной нулю. Рассмотрим некоторый пример:

Строка: aacaacaaa
Значение:010123452
a - нет собственных суффиксов
aa - максимальный собственный суффикс равен a=a
aac - нет собственного суффикса, который бы совпадал с префиксом
aaca - последняя a является максимальным суффиксом, который совпадает с первой a
aacaa - первые две a совпадаю с последними двумя a
aacaac - aac=aac
aacaaca - aaca=aaca
aacaacaa - aacaa=aacaa
aacaacaaa - aa = aa

Тривиальный алгоритм нахождения префикс функции выглядел бы как цикл по i от 0 до длины строки, внутри которого перебирается некое временное значение префикс функции, назовем его k, от 0 до i, где k — является истинным значением префикс функции, если выполняется условие, что подстрока с 0 до k, равна подстроке c i-k до k, т.е суффикс и префикс совпадают:

for(int i = 0; i < s.size; i++) for(int k = 0; k < i; k++) if(префикс длины k равен суффиксу длины k) берем k как ответ

Данный способ подсчета достаточный медленный, но можно заметить, что значение префикс функции либо увеличивается на 1, либо уменьшается. Таким образом значение префикс функции на i шаге меньше или равно значение на i-1 шаге плюс 1. Допустим, что это не так, тогда P[i]>P[i-1]+1. Возьмем суффикс, при котором мы получили такое значение P[i] и удалим из него последний символ. Мы получили суффикс, который заканчивается в позиции i-1 и имеет длину лучше, чем рассматриваемый нами для P[i-1], что приводит к противоречию.
Несложно заметить, что префикс функция растет, когда следующий символ совпадает, т.е s[i]=s[k]. И наоборот, префикс функция падает, когда они не равны. Для того, чтобы найти значение префикс функции быстро, необходимо найти такое максимальное k, для которого будут выполнятся свойства префикс функции. Тогда, если мы научимся находить такое k, то достаточно будет проверить равенство s[i] и s[k] символов, и если они совпадают, то мы нашли ответ, иначе следует найти следующее k. Для нахождения k, мы можем воспользоваться информацией, полученной на предыдущих шагах, а именно, следующее значение k есть ничто иное как P[k-1].
Префикс функция применяется, как основа для алгоритмов поиска подстроки в строке.

Научиться программировать

  • на Delphi

  • на Java

  • на C++

geekbrains.ru/
geekbrains.ru/