|
|
| Строка 1: |
Строка 1: |
| − | ==Определение==
| + | Префикс-функция строки <tex>s</tex> {{---}} функция <tex>\pi(k) = max \{ j | j \leq k,</tex> <tex>s[0..j - 1] = s[k - j + 1..k] \}</tex>. |
| − | Префикс-функцией цепочки <tex>S</tex> называется функция <tex>\pi(k) = max \{ j | j \leq k</tex> и <tex>s[0..j - 1] = s[k - j + 1..k] \}</tex> | |
| | | | |
| − | ==Алгоритм вычисления== | + | ==Алгоритм== |
| − | <tex> n = |S|</tex>
| + | Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. |
| − | *'''Псевдокод'''
| + | ===Пример=== |
| − | k = 0
| + | Рассмотрим строку abcabcd, для которой префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>. |
| − | <tex>\pi</tex>(0) = 0
| + | {| class="wikitable" |
| − | for (i = 1 .. (n - 1)) {
| + | ! Шаг || Строка || Значение функции |
| − | while (k > 0 && s[i] <tex>\ne</tex> s[k])
| + | |- |
| − | k = <tex>\pi</tex>(k - 1)
| + | | <tex>1</tex> || a || 0 |
| − | if (s[i] == s[k])
| + | |- |
| − | k = k + 1
| + | | <tex>2</tex> || ab || 0 |
| − | <tex>\pi</tex>(i) = k
| + | |- |
| − | }
| + | | <tex>3</tex> || abc || 0 |
| − | *'''Корректность работы'''
| + | |- |
| − | [[Файл:Prefix1.jpg|center]]
| + | | <tex>4</tex> || abca || 1 |
| − | Как видно из рисунка, при совпадении символов <tex>S[k]</tex> и <tex>S[i]</tex> длина наибольшего общего префикса увеличивается на 1. В случае, когда символы <tex>S[k]</tex> и <tex>S[i]</tex> не совпадают, <tex>\pi(k-1)</tex> - следующая по максимальности длина потенциального наибольшего общего префикса
| + | |- |
| − | | + | | <tex>5</tex> || abcab || 2 |
| − | *'''Время работы'''
| + | |- |
| − | Сперва отметим очевидный из определения факт: <tex>\pi(k + 1) - \pi(k) \leq 1</tex> для любого <tex>k</tex>. В самом деле, в противном случае <tex>\pi(k)</tex> не максимально.
| + | | <tex>6</tex> || abcabc || 3 |
| − | Теперь рассмотрим произвольную итерацию внешнего цикла <tex>for</tex>. Возможно одно из трёх:
| + | |- |
| − | 1) <tex>s[i] = s[k]</tex>. Тогда значение <tex>k</tex> увеличивается на 1, цикл <tex>while</tex> не итерируется
| + | | <tex>7</tex> || abcabcd || 0 |
| − | 2) <tex>k = 0</tex> <tex>\&</tex> <tex>s[i] \ne s[k]</tex>. Тогда значение <tex>k</tex> не изменяется, цикл <tex>while</tex> не итерируется
| + | |} |
| − | 3) <tex>while</tex> итерируется хотя бы раз. При каждой итерации <tex>while</tex> значение <tex>k</tex> может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций <tex>while</tex> для всех итераций <tex>for</tex> не превышает <tex>n</tex>
| |
| − | Таким образом, общее время работы - <tex>O(n)</tex>.
| |
Префикс-функция строки [math]s[/math] — функция [math]\pi(k) = max \{ j | j \leq k,[/math] [math]s[0..j - 1] = s[k - j + 1..k] \}[/math].
Алгоритм
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
Пример
Рассмотрим строку abcabcd, для которой префикс-функции равно [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
|
