Префикс-функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
м (rollbackEdits.php mass rollback)
 
(не показаны 193 промежуточные версии 18 участников)
Строка 1: Строка 1:
Префикс-функция строки <tex>s</tex> {{---}} функция <tex>\pi(i) = \max\limits_{k = 1..i - 1} \{ 0, k : </tex> <tex>s[1..k] = s[i - k + 1..i] \}</tex>.
+
{{Определение
==Алгоритм==
+
|definition = '''Префикс-функция''' ''(англ. prefix-function)'' от строки {{---}} массив длин наибольших [[Период_и_бордер,_их_связь#Определения|бордеров]] для каждой позиции этой строки}}
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
+
Здесь и далее считаем, что символы в строках нумеруются с <tex>0</tex>.
 +
 
 +
Определим префикс-функцию от строки <tex>s</tex> в позиции <tex>i</tex> следующим образом: <tex>\pi(s, i) = \max\limits_{k = 1 \ldots i} \{k : </tex> <tex>s[0 \ldots k - 1] = s[i - k + 1 \ldots i] \}</tex>. Если мы не нашли такого <tex>k</tex>, то <tex>\pi(s, i)=0</tex>.
 +
 
 +
==Наивный алгоритм==
 +
Наивный алгоритм вычисляет префикс-функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за <tex>n</tex>. Будем считать, что префикс-функция хранится в массиве <tex> p </tex>.  
  
 
===Псевдокод===
 
===Псевдокод===
  '''Prefix_function''' (<tex>s</tex>)
+
  '''int'''[] prefixFunction('''string''' s):
       <tex>\pi</tex> = [0,..,0]
+
       '''int'''[] p = '''int'''[s.length]
       '''for''' i = 1 '''to''' n
+
      fill(p, 0)
           '''for''' k = 1 '''to''' i - 1
+
       '''for''' i = 0 '''to''' s.length - 1
               '''if''' s[1..k] == s[i - k + 1..i]
+
           '''for''' k = 0 '''to''' i - 1
                   <tex>\pi</tex>[i] = k
+
               '''if''' s[0..k] == s[i - k..i]
       '''return''' <tex>\pi</tex>
+
                   p[i] = k
 +
       '''return''' p
  
 
===Пример===
 
===Пример===
Рассмотрим строку abcabcd, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
+
Рассмотрим строку <tex>abcabcd</tex>, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
 
{| class="wikitable"
 
{| class="wikitable"
 
! Шаг || Строка || Значение функции
 
! Шаг || Строка || Значение функции
Строка 35: Строка 41:
 
Всего <tex>O(n^2)</tex> итераций цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.
 
Всего <tex>O(n^2)</tex> итераций цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.
  
==Оптимизация==
+
==Эффективный алгоритм==
 
Вносятся несколько важных замечаний:
 
Вносятся несколько важных замечаний:
*Следует заметить, что <tex>\pi(i) \le \pi(i-1) + 1</tex>. По определению префикс функции верно, что <tex>s[1..\pi(i)] = s[i - \pi(i) + 1..i]</tex>. В частности, получается, что <tex>s[1..\pi(i) - 1] = s[i - \pi(i) + 1..i - 1]</tex>. Поскольку <tex>\pi</tex> это наибольший префикс равный суффиксу, то <tex>\pi(i - 1) \ge \pi(i) - 1</tex>.  
+
* Заметим, что <tex>p[i + 1] \leqslant p[i] + 1</tex>. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции <tex>i + 1</tex> и имеющий длину <tex>p[i + 1]</tex>, удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции <tex>i</tex> и имеющий длину <tex>p[i + 1] - 1</tex>, следовательно неравенство <tex>p[i + 1] > p[i] + 1</tex> неверно.
*Избавимся от явных сравнений строк. Для этого подберем такое <tex>k</tex>, что <tex>k = \pi(i) - 1</tex>. Делаем это следующим образом. За исходное <tex>k</tex> необходимо взять <tex>\pi(i - 1)</tex>, что следует из первого пункта. В случае, когда символы <tex>s[k+1]</tex> и <tex>s[i]</tex> не совпадают, <tex>\pi(k)</tex> {{---}} следующее потенциальное наибольшее значение <tex>k</tex>, что видно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение. Если <tex>k=0</tex>, то <tex>\pi(i)=1</tex> при <tex>s[i] = s[1]</tex> , иначе <tex>\pi(i)=0</tex>.
+
* Избавимся от явных сравнений строк. Пусть мы вычислили <tex>p[i]</tex>, тогда, если <tex>s[i + 1] = s[p[i]]</tex>, то <tex>p[i + 1] = p[i] + 1</tex>. Если окажется, что <tex>s[i + 1] \ne s[p[i]]</tex>, то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому [[Период_и_бордер,_их_связь#Определения|бордеру]] наибольшей длины, для этого подберем такое <tex>k</tex>, что <tex>k = p[i] - 1</tex>. Делаем это следующим образом. За исходное <tex>k</tex> необходимо взять <tex>p[i - 1]</tex>, что следует из первого пункта. В случае, когда символы <tex>s[k]</tex> и <tex>s[i]</tex> не совпадают, <tex>p[k - 1]</tex> {{---}} следующее потенциальное наибольшее значение <tex>k</tex>, что видно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение. Если <tex>k=0</tex>, то <tex>p[i]=1</tex> при <tex>s[i] = s[1]</tex> , иначе <tex>p[i]=0</tex>.
 +
 
 +
[[Файл:mprfx.jpg|800px]]
  
[[Файл:Prefix2.jpg‎]]
 
 
===Псевдокод===
 
===Псевдокод===
  '''Prefix_function''' (<tex>s</tex>)
+
  '''int'''[] prefixFunction('''string''' s):
      <tex>\pi</tex>[1] = 0
+
  p[0] = 0
      k = 0
+
  '''for''' i = 1 '''to''' s.length - 1
      '''for''' i = 2 '''to''' n
+
      k = p[i - 1]
          '''while''' k > 0 && s[i] != s[k + 1]
+
      '''while''' k > 0 '''and''' s[i] != s[k]
              k = <tex>\pi</tex>[k]
+
          k = p[k - 1]
          '''if''' s[i] == s[k + 1]
+
      '''if''' s[i] == s[k]
              k++
+
          k++
          <tex>\pi</tex>[i] = k
+
      p[i] = k
      '''return''' <tex>\pi</tex>
+
  '''return''' p
  
 
===Время работы===
 
===Время работы===
Время работы алгоритма составит <tex>O(n)</tex>. Для доказательства этого нужно заметить, что итоговое количество итераций цикла <tex>while</tex> определяет асимптотику алгоритма. Теперь стоит отметить, что <tex>k</tex> увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение <tex>k = n - 1</tex>. Поскольку внутри цикла <tex>while</tex> значение <tex>k</tex> лишь уменьшается, получается, что <tex>k</tex> не может суммарно уменьшиться больше, чем <tex>n-1</tex> раз. Значит цикл <tex>while</tex> в итоге выполнится не более <tex>n</tex> раз, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>.
+
Время работы алгоритма составит <tex>O(n)</tex>. Для доказательства этого нужно заметить, что итоговое количество итераций цикла <tex>\mathrm{while}</tex> определяет асимптотику алгоритма. Теперь стоит отметить, что <tex>k</tex> увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение <tex>k = n - 1</tex>. Поскольку внутри цикла <tex>\mathrm{while}</tex> значение <tex>k</tex> лишь уменьшается, получается, что <tex>k</tex> не может суммарно уменьшиться больше, чем <tex>n-1</tex> раз. Значит цикл <tex>\mathrm{while}</tex> в итоге выполнится не более <tex>n</tex> раз, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>.
 +
 
 +
== Построение префикс-функции по Z-функции==
 +
=== Постановка задачи ===
 +
Дан массив с корректной [[Z-функция | Z-функцией]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с префикс-функцией для строки <tex>s</tex>.
 +
 
 +
=== Описание алгоритма ===
 +
Пусть Z-функция хранится в массиве <tex>z[0 \ldots n-1]</tex>. Префикс-функцию будем записывать в массив <tex>p[0 \ldots n-1]</tex>.
 +
Заметим, что если <tex>z[i] > 0, </tex> то для всех элементов с индексом <tex>i + j</tex>, где <tex>0 \leqslant j < z[i] </tex>,  значение <tex>p[i + j] </tex> будет не меньше, чем длина подстроки с <tex> i </tex> по <tex> i + j</tex>, что равно <tex>j + 1</tex> (как изображено на рисунке).
 +
 
 +
Также заметим, что если мы уже установили в какую-то позицию значение <tex> j </tex> с позиции <tex> i </tex>, а потом пытаемся установить значение <tex> j' </tex> c позиции <tex> i' </tex>, причём <tex> i < i' </tex> и <tex> i + j = i' + j' </tex>, то изменение с позиции <tex> i' </tex> только уменьшит значение <tex> p[i + j]</tex>. Действительно, значение после первого присвоения <tex>p[i + j] = j > j' = p[i' + j']</tex>. В итоге получаем алгоритм: идем слева направо по массиву <tex>z</tex> и, находясь на позиции <tex>i</tex>, пытаемся записать в <tex>p</tex> от позиции <tex>i + z[i] - 1 </tex> до  <tex>i</tex> значение <tex> j + 1,</tex> где <tex>j</tex> пробегает все значения <tex> 0 \dots z[i] - 1</tex>, пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию.
 +
 
 +
Убедимся, что алгоритм работает за линейное время (см. псевдокод). Каждый элемент устанавливается ровно один раз. Дальше на нем может случиться только <tex>\mathrm{break}</tex>. Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений и количество <tex>\mathrm{break}</tex>. Количество установленных значений {{---}} <tex> n</tex>. А число <tex>\mathrm{break}</tex> тоже будет не больше <tex>n</tex>, так как каждый <tex>\mathrm{break}</tex> переводит внешний цикл на следующую итерацию, откуда получаем итоговую асимптотику <tex>O(n)</tex>.
 +
 
 +
[[Файл:ZP4.jpg|800px]]
 +
 
 +
=== Псевдокод ===
 +
'''int'''[] buildPrefixFunctionFromZFunction('''int'''[] z):
 +
  '''int'''[] p = '''int'''[z.length]
 +
  fill(p, 0)
 +
  '''for''' i = 1 '''to''' z.length - 1
 +
    '''for''' j = z[i] - 1 '''downto''' 0
 +
      '''if''' p[i + j] > 0
 +
        '''break'''
 +
      '''else'''
 +
        p[i + j] = j + 1
 +
  '''return''' p
  
 
==Построение строки по префикс-функции==
 
==Построение строки по префикс-функции==
 
===Постановка задачи===  
 
===Постановка задачи===  
Восстановить строку по префикс-функции за <tex>O(N)</tex> (алфавит неограничен).
+
Восстановить строку по префикс-функции за <tex>O(n)</tex>, считая алфавит неограниченным.
  
 
===Описание алгоритма===
 
===Описание алгоритма===
 
Пусть в массиве <tex>p</tex> хранятся значения префикс-функции, в <tex>s</tex> будет записан ответ. Пойдем по массиву <tex>p</tex> слева направо.
 
Пусть в массиве <tex>p</tex> хранятся значения префикс-функции, в <tex>s</tex> будет записан ответ. Пойдем по массиву <tex>p</tex> слева направо.
Пусть мы хотим узнать значение <tex>s[i]</tex>, посмотрим на значение <tex>p[i]</tex> если <tex>p[i] =0</tex> тогда в <tex>s[i]</tex> запишем новый символ, иначе <tex>s[i] = s[p[i]]</tex>. Обратим внимание, что  <tex>s[p[i]]</tex> мы посчитали раньше <tex>(</tex>т.к <tex>p[i] \leqslant  i)</tex>. Так как подстрока с <tex>1</tex> по <tex>p[i]</tex> заканчивается в <tex>s[i]</tex>, то <tex>s[i]</tex> должен быть равен <tex>s[p[i]]</tex>.
 
  
===Псевдокод===
+
Пусть мы хотим узнать значение <tex>s[i]</tex>. Для этого посмотрим на значение <tex>p[i]</tex>: если <tex>p[i] =0</tex>, тогда в <tex>s[i]</tex> запишем новый символ, иначе <tex>s[i] = s[p[i] - 1]</tex>. Обратим внимание, что  <tex>s[p[i] - 1]</tex> нам уже известно, так как <tex>p[i] - 1 < i</tex>.
  '''string''' s;
+
 
vector<'''int'''> p;
+
=== Реализация ===
'''for''' i = 0 '''to''' p.size - 1
+
  '''string''' buildFromPrefix('''int'''[] p):
    '''if''' p[i] == 0     
+
  s = ""
           s += new char;
+
  '''for''' i = 0 '''to''' p.length - 1
    '''else'''
+
      '''if''' p[i] == 0     
           s += s[p[i]];
+
           s += new character
 +
      '''else'''
 +
           s += s[p[i] - 1]
 +
  '''return''' s
  
 
===Доказательство корректности алгоритма===
 
===Доказательство корректности алгоритма===
 
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.
 
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.
  
Воспользуемся старыми обозначениями <tex>p</tex> данная префикс-функция, <tex>s</tex> правильная строка, <tex>s1</tex> эту строку построил наш алгоритм, <tex> q </tex> массив значений префикс-функции для <tex>s1</tex>.
+
Пусть <tex>p</tex> {{---}} данная префикс-функция, строку <tex>s</tex> построил наш алгоритм, <tex> q </tex> {{---}} массив значений префикс-функции для <tex>s</tex>.
 +
 
 +
Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива <tex> q </tex> прибавление нового символа не влияет, так как при подсчёте префикс-функции на <tex> i </tex>-ой позиции рассматриваются символы на позициях не больше <tex> i </tex>. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.
 +
* База очевидна для строки длины <tex>1</tex>.
 +
* Переход: пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[0 \ldots n - 1] = q[0 \ldots n - 1]</tex>. Возможны два случая:
 +
**  <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.
 +
** <tex>p[n] > 0</tex>. Бордер строки <tex> s[0 \ldots n - 1] </tex> имеет длину <tex> p[n-1] = q[n-1] </tex>. Поэтому если дописать к строке <tex> s </tex> символ <tex> s[q[n] - 1] </tex>, то бордер нашей новой строки <tex> s[0 \ldots n] </tex> станет равен <tex> p[n] </tex>, как можно увидеть на [[Префикс-функция#Эффективный алгоритм | рисунке]].
 +
 
 +
== Критерий корректности значений префикс-функции ==
 +
{{Задача
 +
|definition = Дан массив значений префикс-функции некоторой строки <tex>s</tex>, необходимо проверить, корректен ли он за <tex>O(|s|)</tex>. Так же узнать размер минимального алфавита, при котором он корректен.
 +
}}
 +
 
 +
=== Решение ===
 +
Если выполняется неравенство <tex>0 \leqslant p[i + 1] \leqslant p[i] + 1</tex>, то мы можем построить строку из алгоритма выше, значит префикс-функция корректна.
  
Докажем корректность по индукции.
+
Найдем минимальный алфавит, при котором префикс-функция корректна. Если значение префикс-функции в текущей ячейке больше нуля, буква известна и алфавит не нуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов. Если все уже известные буквы использованы, понятно что, необходимо добавить новую букву.
  
База очевидна для строки длиной <tex>1</tex>.
+
=== Доказательство корректности ===
 +
Докажем, что найденнный выше алфавит минимален от противного. Допустим, существует строка, использующая алфавит меньшей мощности. Рассмотрим первое вхождение буквы, которая есть в нашем алфавите, а в их отсутствует. Понятно, что для этого символа префикс-функция равна 0, т.к. мы добавили новую букву. Пройдемся циклом <tex>\mathrm{while}</tex> по подпрефиксам. Т.к. в меньшем решении буква не новая, то она увеличит подпрефикс и префикс-функция в новой строке будет отличаться от нуля в этом символе, а должна равняться нулю. Противоречие, следовательно не существует алфаивта меньшей мощности, чем найденный алгоритмом выше.
  
Переход: Пусть до <tex>n</tex> позиции мы построили строку, что <tex>p[1..n - 1] = q[1..n - 1]</tex>. Возможно два варианта,
+
=== Псевдокод ===
 +
'''bool''' is_correct('''int'''[] p):
 +
  '''for''' i = 0 '''to''' p.length - 1
 +
      '''if''' i > 0 && p[i] > p[i - 1] + 1 || p[i] < 0
 +
          '''return''' '''false'''         
 +
  '''return''' '''true'''
  
1) <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.
+
'''int''' minimal_alphabet('''int'''[] p):
 +
  c = 1
 +
  s[0] = 0
 +
  '''for''' i = 1 '''to''' p.length - 1
 +
        '''if''' p[i] == 0
 +
          '''fill'''(used, false)
 +
          k = p[i - 1]            
 +
          '''while''' k > 0
 +
              used[s[k]] = '''true'''
 +
              k = p[k - 1]
 +
          s[i] = -1
 +
          '''for''' j = 1 '''to''' c
 +
              '''if''' !used[j]
 +
                  s[i] = j;
 +
                  '''break'''
 +
          '''if''' s[i] == -1
 +
              s[i] = c++ 
 +
        '''else'''
 +
          s[i] = s[p[i] - 1]                   
 +
  '''return''' c
  
2) <tex>p[n] > 0</tex>. Предположим, что <tex>q[n] \neq p[n] </tex>. Заметим, что подстрока с <tex>1</tex> по <tex>p[n]</tex> оканчивается на <tex>n</tex>-ом символе, соответственно, <tex>q[n] > p[n]</tex>. Но этого не может быть, так как тогда бы в строке <tex>s</tex> существовала большая подстрока оканчивающаяся на <tex>n</tex> символе, что противоречит тому что массив <tex>p</tex> корректный.  
+
== См. также ==
 +
*[[Z-функция|Z-функция]]
 +
*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
 +
== Источники информации ==
 +
*[[wikipedia:ru:Префикс-функция | Википедия {{---}} Префикс-функция]]
 +
*[http://e-maxx.ru/algo/prefix_function MAXimal :: algo :: Префикс-функция]
 +
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296 ISBN 978-5-8459-0857-5
  
Простой пример некорректного <tex>p = {0,1,1} </tex>, тогда по алгоритму получится строка <tex>aaa</tex>. Очевидно, что префикс-функции не будут совпадать.
 
  
== Литература ==
+
[[Категория: Алгоритмы и структуры данных]]
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.
+
[[Категория: Поиск подстроки в строке]]
 +
[[Категория:Точный поиск]]

Текущая версия на 19:33, 4 сентября 2022

Определение:
Префикс-функция (англ. prefix-function) от строки — массив длин наибольших бордеров для каждой позиции этой строки

Здесь и далее считаем, что символы в строках нумеруются с [math]0[/math].

Определим префикс-функцию от строки [math]s[/math] в позиции [math]i[/math] следующим образом: [math]\pi(s, i) = \max\limits_{k = 1 \ldots i} \{k : [/math] [math]s[0 \ldots k - 1] = s[i - k + 1 \ldots i] \}[/math]. Если мы не нашли такого [math]k[/math], то [math]\pi(s, i)=0[/math].

Наивный алгоритм

Наивный алгоритм вычисляет префикс-функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за [math]n[/math]. Будем считать, что префикс-функция хранится в массиве [math] p [/math].

Псевдокод

int[] prefixFunction(string s):
     int[] p = int[s.length]
     fill(p, 0)
     for i = 0 to s.length - 1
         for k = 0 to i - 1
             if s[0..k] == s[i - k..i]
                 p[i] = k
     return p

Пример

Рассмотрим строку [math]abcabcd[/math], для которой значение префикс-функции равно [math][0,0,0,1,2,3,0][/math].

Шаг Строка Значение функции
[math]1[/math] a 0
[math]2[/math] ab 0
[math]3[/math] abc 0
[math]4[/math] abca 1
[math]5[/math] abcab 2
[math]6[/math] abcabc 3
[math]7[/math] abcabcd 0

Время работы

Всего [math]O(n^2)[/math] итераций цикла, на каждой из который происходит сравнение строк за [math]O(n)[/math], что дает в итоге [math]O(n^3)[/math].

Эффективный алгоритм

Вносятся несколько важных замечаний:

  • Заметим, что [math]p[i + 1] \leqslant p[i] + 1[/math]. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции [math]i + 1[/math] и имеющий длину [math]p[i + 1][/math], удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции [math]i[/math] и имеющий длину [math]p[i + 1] - 1[/math], следовательно неравенство [math]p[i + 1] \gt p[i] + 1[/math] неверно.
  • Избавимся от явных сравнений строк. Пусть мы вычислили [math]p[i][/math], тогда, если [math]s[i + 1] = s[p[i]][/math], то [math]p[i + 1] = p[i] + 1[/math]. Если окажется, что [math]s[i + 1] \ne s[p[i]][/math], то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому бордеру наибольшей длины, для этого подберем такое [math]k[/math], что [math]k = p[i] - 1[/math]. Делаем это следующим образом. За исходное [math]k[/math] необходимо взять [math]p[i - 1][/math], что следует из первого пункта. В случае, когда символы [math]s[k][/math] и [math]s[i][/math] не совпадают, [math]p[k - 1][/math] — следующее потенциальное наибольшее значение [math]k[/math], что видно из рисунка. Последнее утверждение верно, пока [math]k\gt 0[/math], что позволит всегда найти его следующее значение. Если [math]k=0[/math], то [math]p[i]=1[/math] при [math]s[i] = s[1][/math] , иначе [math]p[i]=0[/math].

Mprfx.jpg

Псевдокод

int[] prefixFunction(string s):
  p[0] = 0
  for i = 1 to s.length - 1
      k = p[i - 1]
      while k > 0 and s[i] != s[k]
          k = p[k - 1]
      if s[i] == s[k]
          k++
      p[i] = k
  return p

Время работы

Время работы алгоритма составит [math]O(n)[/math]. Для доказательства этого нужно заметить, что итоговое количество итераций цикла [math]\mathrm{while}[/math] определяет асимптотику алгоритма. Теперь стоит отметить, что [math]k[/math] увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение [math]k = n - 1[/math]. Поскольку внутри цикла [math]\mathrm{while}[/math] значение [math]k[/math] лишь уменьшается, получается, что [math]k[/math] не может суммарно уменьшиться больше, чем [math]n-1[/math] раз. Значит цикл [math]\mathrm{while}[/math] в итоге выполнится не более [math]n[/math] раз, что дает итоговую оценку времени алгоритма [math]O(n)[/math].

Построение префикс-функции по Z-функции

Постановка задачи

Дан массив с корректной Z-функцией для строки [math]s[/math], получить за [math]O(n)[/math] массив с префикс-функцией для строки [math]s[/math].

Описание алгоритма

Пусть Z-функция хранится в массиве [math]z[0 \ldots n-1][/math]. Префикс-функцию будем записывать в массив [math]p[0 \ldots n-1][/math]. Заметим, что если [math]z[i] \gt 0, [/math] то для всех элементов с индексом [math]i + j[/math], где [math]0 \leqslant j \lt  z[i] [/math], значение [math]p[i + j] [/math] будет не меньше, чем длина подстроки с [math] i [/math] по [math] i + j[/math], что равно [math]j + 1[/math] (как изображено на рисунке).

Также заметим, что если мы уже установили в какую-то позицию значение [math] j [/math] с позиции [math] i [/math], а потом пытаемся установить значение [math] j' [/math] c позиции [math] i' [/math], причём [math] i \lt i' [/math] и [math] i + j = i' + j' [/math], то изменение с позиции [math] i' [/math] только уменьшит значение [math] p[i + j][/math]. Действительно, значение после первого присвоения [math]p[i + j] = j \gt j' = p[i' + j'][/math]. В итоге получаем алгоритм: идем слева направо по массиву [math]z[/math] и, находясь на позиции [math]i[/math], пытаемся записать в [math]p[/math] от позиции [math]i + z[i] - 1 [/math] до [math]i[/math] значение [math] j + 1,[/math] где [math]j[/math] пробегает все значения [math] 0 \dots z[i] - 1[/math], пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию.

Убедимся, что алгоритм работает за линейное время (см. псевдокод). Каждый элемент устанавливается ровно один раз. Дальше на нем может случиться только [math]\mathrm{break}[/math]. Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений и количество [math]\mathrm{break}[/math]. Количество установленных значений — [math] n[/math]. А число [math]\mathrm{break}[/math] тоже будет не больше [math]n[/math], так как каждый [math]\mathrm{break}[/math] переводит внешний цикл на следующую итерацию, откуда получаем итоговую асимптотику [math]O(n)[/math].

ZP4.jpg

Псевдокод

int[] buildPrefixFunctionFromZFunction(int[] z):
  int[] p = int[z.length]
  fill(p, 0)
  for i = 1 to z.length - 1
    for j = z[i] - 1 downto 0
      if p[i + j] > 0 
        break
      else
        p[i + j] = j + 1
  return p

Построение строки по префикс-функции

Постановка задачи

Восстановить строку по префикс-функции за [math]O(n)[/math], считая алфавит неограниченным.

Описание алгоритма

Пусть в массиве [math]p[/math] хранятся значения префикс-функции, в [math]s[/math] будет записан ответ. Пойдем по массиву [math]p[/math] слева направо.

Пусть мы хотим узнать значение [math]s[i][/math]. Для этого посмотрим на значение [math]p[i][/math]: если [math]p[i] =0[/math], тогда в [math]s[i][/math] запишем новый символ, иначе [math]s[i] = s[p[i] - 1][/math]. Обратим внимание, что [math]s[p[i] - 1][/math] нам уже известно, так как [math]p[i] - 1 \lt i[/math].

Реализация

string buildFromPrefix(int[] p):
  s = "" 
  for i = 0 to p.length - 1
      if p[i] == 0     
          s += new character
      else
          s += s[p[i] - 1]
  return s

Доказательство корректности алгоритма

Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.

Пусть [math]p[/math] — данная префикс-функция, строку [math]s[/math] построил наш алгоритм, [math] q [/math] — массив значений префикс-функции для [math]s[/math].

Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива [math] q [/math] прибавление нового символа не влияет, так как при подсчёте префикс-функции на [math] i [/math]-ой позиции рассматриваются символы на позициях не больше [math] i [/math]. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.

  • База очевидна для строки длины [math]1[/math].
  • Переход: пусть до [math]n[/math]-ой позиции мы построили строку, что [math]p[0 \ldots n - 1] = q[0 \ldots n - 1][/math]. Возможны два случая:
    • [math]p[n] = 0[/math]. Тогда мы добавляем новый символ, поэтому [math]q[n][/math] тоже будет равно [math]0[/math].
    • [math]p[n] \gt 0[/math]. Бордер строки [math] s[0 \ldots n - 1] [/math] имеет длину [math] p[n-1] = q[n-1] [/math]. Поэтому если дописать к строке [math] s [/math] символ [math] s[q[n] - 1] [/math], то бордер нашей новой строки [math] s[0 \ldots n] [/math] станет равен [math] p[n] [/math], как можно увидеть на рисунке.

Критерий корректности значений префикс-функции

Задача:
Дан массив значений префикс-функции некоторой строки [math]s[/math], необходимо проверить, корректен ли он за [math]O(|s|)[/math]. Так же узнать размер минимального алфавита, при котором он корректен.


Решение

Если выполняется неравенство [math]0 \leqslant p[i + 1] \leqslant p[i] + 1[/math], то мы можем построить строку из алгоритма выше, значит префикс-функция корректна.

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

Доказательство корректности

Докажем, что найденнный выше алфавит минимален от противного. Допустим, существует строка, использующая алфавит меньшей мощности. Рассмотрим первое вхождение буквы, которая есть в нашем алфавите, а в их отсутствует. Понятно, что для этого символа префикс-функция равна 0, т.к. мы добавили новую букву. Пройдемся циклом [math]\mathrm{while}[/math] по подпрефиксам. Т.к. в меньшем решении буква не новая, то она увеличит подпрефикс и префикс-функция в новой строке будет отличаться от нуля в этом символе, а должна равняться нулю. Противоречие, следовательно не существует алфаивта меньшей мощности, чем найденный алгоритмом выше.

Псевдокод

bool is_correct(int[] p):
  for i = 0 to p.length - 1
      if i > 0 && p[i] > p[i - 1] + 1 || p[i] < 0
          return false           
  return true
int minimal_alphabet(int[] p):
  c = 1
  s[0] = 0
  for i = 1 to p.length - 1
       if p[i] == 0
          fill(used, false)
          k = p[i - 1]              
          while k > 0
              used[s[k]] = true
              k = p[k - 1]
          s[i] = -1
          for j = 1 to c
              if !used[j]
                  s[i] = j;
                  break
          if s[i] == -1
              s[i] = c++  
       else
          s[i] = s[p[i] - 1]                    
  return c

См. также

Источники информации