Викиконспекты - Вклад участника [ru]

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

2012-05-13T09:52:16Z

89.110.14.141: /* Оптимизация */

Префикс-функция строки <tex>s</tex> {{---}} функция <tex>\pi(i) = max \{ k | k < i,</tex> <tex>s[1..k] = s[i - k + 1..i] \}</tex>.

==Алгоритм==
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
===Пример===
Рассмотрим строку abcabcd, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
{| class="wikitable"
! Шаг || Строка || Значение функции
|-
| <tex>1</tex> || a || 0
|-
| <tex>2</tex> || ab || 0
|-
| <tex>3</tex> || abc || 0
|-
| <tex>4</tex> || abca || 1
|-
| <tex>5</tex> || abcab || 2
|-
| <tex>6</tex> || abcabc || 3
|-
| <tex>7</tex> || abcabcd || 0
|}

===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex> = []
'''for''' i = 1 '''to''' n
'''for''' k = 1 '''to''' i - 1
'''if''' s[1..k] == s[i - k + 1..i]
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>

===Время работы===
Всего <tex>O(n^2)</tex> итераций цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.

==Оптимизация==
Внесем несколько важных замечаний:
*<tex>\pi(i)</tex> превосходит <tex>\pi(i-1)</tex> не больше, чем на <tex>1</tex>. Действительно, если <tex>\pi(i) > \pi(i-1) + 1</tex>, тогда <tex>\pi(i) - 1 > \pi(i-1)</tex>, значит в <tex>\pi(i-1)</tex> не максимально возможное значение, получили противоречие.
*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi(i-1)</tex> и <tex>s[\pi(i-1) + 1] = s[i]</tex>, тогда очевидно <tex>\pi(i) = \pi(i-1) + 1</tex>. Если же условие <tex>s[\pi(i) + 1] = s[i + 1]</tex> ложно, то хотелось бы найти наибольшую длину <tex> k</tex>, для которой верно <tex>\pi(i) = k + 1</tex>. Когда мы найдем такое <tex>k</tex> нам достаточно будет сравнить <tex>s[k + 1]</tex> и <tex>s[i]</tex>, при их равенстве <tex>\pi(i) = k + 1</tex> будет верно. Будем искать наше <tex>k</tex> пока оно больше нуля, при равенстве нулю <tex>\pi(i) = 1</tex>, если <tex>s[i] = s[1]</tex>, иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать <tex>k</tex>.
*Для поиска <tex>k</tex> нам стоит использовать равенство <tex>k = \pi(k)</tex>, когда <tex>s[k+1] = s[i]</tex> ложно, взяв за исходное <tex> k = \pi(i -1)</tex>, это позволит выбирать <tex>k</tex> по убыванию вплоть до нуля, так как очевидно, что <tex>\pi(x) \geq \pi(\pi(x))</tex> для любых <tex>x</tex>.
Последние два пункта наглядно проиллюстрированы на рисунке:

[[Файл:Prefix2.jpg‎]]
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex> = 0
'''for''' i = 2 '''to''' n
k = <tex>\pi</tex>[i - 1]
'''while''' k > 0 && s[i] != s[k + 1]
k = <tex>\pi</tex>[k]
'''if''' s[i] == s[k + 1]
k++
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>

===Время работы===
В итоге мы получили алгоритм выполняющий <tex>O(n)</tex> итераций за <tex>O(1)</tex>, что дает нам итоговое <tex>O(n)</tex>.

== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.

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

2012-05-13T09:51:11Z

89.110.14.141: /* Псевдокод */

Префикс-функция строки <tex>s</tex> {{---}} функция <tex>\pi(i) = max \{ k | k < i,</tex> <tex>s[1..k] = s[i - k + 1..i] \}</tex>.

==Алгоритм==
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
===Пример===
Рассмотрим строку abcabcd, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
{| class="wikitable"
! Шаг || Строка || Значение функции
|-
| <tex>1</tex> || a || 0
|-
| <tex>2</tex> || ab || 0
|-
| <tex>3</tex> || abc || 0
|-
| <tex>4</tex> || abca || 1
|-
| <tex>5</tex> || abcab || 2
|-
| <tex>6</tex> || abcabc || 3
|-
| <tex>7</tex> || abcabcd || 0
|}

===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex> = []
'''for''' i = 1 '''to''' n
'''for''' k = 1 '''to''' i - 1
'''if''' s[1..k] == s[i - k + 1..i]
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>

===Время работы===
Всего <tex>O(n^2)</tex> итераций цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.

==Оптимизация==
Внесем несколько важных замечаний:
*<tex>\pi(i)</tex> превосходит <tex>\pi(i-1)</tex> не больше чем на <tex>1</tex>. Действительно, если <tex>\pi(i) > \pi(i-1) + 1</tex>, тогда <tex>\pi(i) - 1 > \pi(i-1)</tex>, значит в <tex>\pi(i-1)</tex> не максимально возможное значение, получили противоречие.
*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi(i-1)</tex> и <tex>s[\pi(i-1) + 1] = s[i]</tex>, тогда очевидно <tex>\pi(i) = \pi(i-1) + 1</tex>. Если же условие <tex>s[\pi(i) + 1] = s[i + 1]</tex> ложно, то хотелось бы найти наибольшую длину <tex> k</tex>, для которой верно <tex>\pi(i) = k + 1</tex>. Когда мы найдем такое <tex>k</tex> нам достаточно будет сравнить <tex>s[k + 1]</tex> и <tex>s[i]</tex>, при их равенстве <tex>\pi(i) = k + 1</tex> будет верно. Будем искать наше <tex>k</tex> пока оно больше нуля, при равенстве нулю <tex>\pi(i) = 1</tex>, если <tex>s[i] = s[1]</tex>, иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать <tex>k</tex>.
*Для поиска <tex>k</tex> нам стоит использовать равенство <tex>k = \pi(k)</tex>, когда <tex>s[k+1] = s[i]</tex> ложно, взяв за исходное <tex> k = \pi(i -1)</tex>, это позволит выбирать <tex>k</tex> по убыванию вплоть до нуля, так как очевидно, что <tex>\pi(x) \geq \pi(\pi(x))</tex> для любых <tex>x</tex>.
Последние два пункта наглядно проиллюстрированы на рисунке:

[[Файл:Prefix2.jpg‎]]
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex> = 0
'''for''' i = 2 '''to''' n
k = <tex>\pi</tex>[i - 1]
'''while''' k > 0 && s[i] != s[k + 1]
k = <tex>\pi</tex>[k]
'''if''' s[i] == s[k + 1]
k++
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>

===Время работы===
В итоге мы получили алгоритм выполняющий <tex>O(n)</tex> итераций за <tex>O(1)</tex>, что дает нам итоговое <tex>O(n)</tex>.

== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.

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

2012-05-13T09:50:42Z

89.110.14.141: /* Псевдокод */

Префикс-функция строки <tex>s</tex> {{---}} функция <tex>\pi(i) = max \{ k | k < i,</tex> <tex>s[1..k] = s[i - k + 1..i] \}</tex>.

==Алгоритм==
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
===Пример===
Рассмотрим строку abcabcd, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
{| class="wikitable"
! Шаг || Строка || Значение функции
|-
| <tex>1</tex> || a || 0
|-
| <tex>2</tex> || ab || 0
|-
| <tex>3</tex> || abc || 0
|-
| <tex>4</tex> || abca || 1
|-
| <tex>5</tex> || abcab || 2
|-
| <tex>6</tex> || abcabc || 3
|-
| <tex>7</tex> || abcabcd || 0
|}

===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex> = 0
'''for''' i = 1 '''to''' n
'''for''' k = 1 '''to''' i - 1
'''if''' s[1..k] == s[i - k + 1..i]
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>

===Время работы===
Всего <tex>O(n^2)</tex> итераций цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.

==Оптимизация==
Внесем несколько важных замечаний:
*<tex>\pi(i)</tex> превосходит <tex>\pi(i-1)</tex> не больше чем на <tex>1</tex>. Действительно, если <tex>\pi(i) > \pi(i-1) + 1</tex>, тогда <tex>\pi(i) - 1 > \pi(i-1)</tex>, значит в <tex>\pi(i-1)</tex> не максимально возможное значение, получили противоречие.
*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi(i-1)</tex> и <tex>s[\pi(i-1) + 1] = s[i]</tex>, тогда очевидно <tex>\pi(i) = \pi(i-1) + 1</tex>. Если же условие <tex>s[\pi(i) + 1] = s[i + 1]</tex> ложно, то хотелось бы найти наибольшую длину <tex> k</tex>, для которой верно <tex>\pi(i) = k + 1</tex>. Когда мы найдем такое <tex>k</tex> нам достаточно будет сравнить <tex>s[k + 1]</tex> и <tex>s[i]</tex>, при их равенстве <tex>\pi(i) = k + 1</tex> будет верно. Будем искать наше <tex>k</tex> пока оно больше нуля, при равенстве нулю <tex>\pi(i) = 1</tex>, если <tex>s[i] = s[1]</tex>, иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать <tex>k</tex>.
*Для поиска <tex>k</tex> нам стоит использовать равенство <tex>k = \pi(k)</tex>, когда <tex>s[k+1] = s[i]</tex> ложно, взяв за исходное <tex> k = \pi(i -1)</tex>, это позволит выбирать <tex>k</tex> по убыванию вплоть до нуля, так как очевидно, что <tex>\pi(x) \geq \pi(\pi(x))</tex> для любых <tex>x</tex>.
Последние два пункта наглядно проиллюстрированы на рисунке:

[[Файл:Prefix2.jpg‎]]
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex> = 0
'''for''' i = 2 '''to''' n
k = <tex>\pi</tex>[i - 1]
'''while''' k > 0 && s[i] != s[k + 1]
k = <tex>\pi</tex>[k]
'''if''' s[i] == s[k + 1]
k++
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>

===Время работы===
В итоге мы получили алгоритм выполняющий <tex>O(n)</tex> итераций за <tex>O(1)</tex>, что дает нам итоговое <tex>O(n)</tex>.

== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.

Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа

2012-05-13T09:46:56Z

89.110.14.141:

Адгоритм Рабина-Карпа предназначен для [[Наивный алгоритм поиска подстроки в строке#Постановка задачи| поиска подстроки в строке]].
==Метод хеширования==

Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать, {{---}} <tex>hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n])</tex> mod <tex>r</tex>, где <tex>p</tex> {{---}} это некоторое простое число, а <tex>r</tex> {{---}} некоторое большое число, чтобы было меньше коллизий (обычно берётся <tex>2^{32}</tex> или <tex>2^{64}</tex>, чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.

При удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за <tex>O(1)</tex>:

<tex>hash(s[i + 1..i + m - 1]) = hash(s[i..i + m - 1]) - p^{m - 1} s[i]</tex>.

<tex>hash(s[i + 1..i + m]) = p \cdot hash(s[i + 1..i + m - 1]) + s[i + m]</tex>.

Получается : <tex>hash(s[i + 1..i + m]) = p \cdot hash(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]</tex>.

==Алгоритм==

Алгоритм начинается с подсчета <tex>hash(s[1..m])</tex> и <tex>hash(p[1..m])</tex>.

Для <tex>i \in [1..n - m + 1]</tex> вычисляется <tex>hash(s[i..i + m - 1]</tex> и сравнивается с <tex>hash(p[1..m])</tex>. Если они оказались равны {{---}} то считается, что подстрока <tex>p</tex> входит в строку <tex>s</tex> (начиная с позиции <tex>i</tex>) или проверяется, что подстрока является шаблоном, для этого выбираются и сравниваются случайные символы из строк.

Для ускорения работы алгоритма оптимально предпосчитать <tex>p^{m}</tex>.

==Псевдокод==
'''RabinKarp''' (s[1..n], p[1..m])
hp = hash(p[1..m])
h = hash(s[1..m])
'''for''' i = 1 '''to''' n - m + 1
'''if''' h = hp
answer.add(i)
h = p * h - p<tex>^{m}</tex> * hash(s[i]) + hash(s[i + m])
'''if''' answer.size() == 0
'''return''' not found
'''else'''
'''return''' answer

Новый хеш <tex>h</tex> был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что <tex>s[n + 1]</tex> {{---}} пустой символ.

==Время работы==

Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>. В цикле всего <tex>n - m + 1</tex> итераций {{---}} каждая выполняется за <tex>O(1)</tex>. Итоговое время работы алгоритма <tex>O(n + m)</tex>.

== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.

==Ссылки==
*[[Наивный алгоритм поиска подстроки в строке]]