Изменения
Новая страница: «{{Определение |definition= Суффиксным массивом для строки <tex>s[1 .. n]</tex> называется такая перестан…»
{{Определение
|definition=
Суффиксным массивом для строки <tex>s[1 .. n]</tex> называется такая перестановка <tex>suf</tex> чисел от <tex>1</tex> до <tex>n</tex>, что <tex>s[suf[i] .. n]</tex> - <tex>i</tex>-ый суффикс в лексикографическом порядке.
}}
Суффиксный массив для строки <tex>s</tex> может быть построен за <tex>O(|s|)</tex>.
== Пример ==
<tex>s = abacaba</tex>. Суффиксы <tex>s</tex> в лексикографическом порядке:<br>
1) <tex>a</tex><br>
2) <tex>aba</tex><br>
3) <tex>abacaba</tex><br>
4) <tex>acaba</tex><br>
5) <tex>ba</tex><br>
6) <tex>bacaba</tex><br>
7) <tex>caba</tex><br>
Значит суффиксный массив для строки <tex>s</tex> равен <tex>suf = \{7, 5, 1, 3, 6, 2, 4\}</tex>
== Применения ==
* Позволяет найти все вхождения образца <tex>p</tex> в строку <tex>s</tex> за время <tex>O(|p| + log(|s|))</tex>
* Позволяет построить массив <tex>lcp</tex> для строки <tex>s</tex> за <tex>O(|s|)</tex>
|definition=
Суффиксным массивом для строки <tex>s[1 .. n]</tex> называется такая перестановка <tex>suf</tex> чисел от <tex>1</tex> до <tex>n</tex>, что <tex>s[suf[i] .. n]</tex> - <tex>i</tex>-ый суффикс в лексикографическом порядке.
}}
Суффиксный массив для строки <tex>s</tex> может быть построен за <tex>O(|s|)</tex>.
== Пример ==
<tex>s = abacaba</tex>. Суффиксы <tex>s</tex> в лексикографическом порядке:<br>
1) <tex>a</tex><br>
2) <tex>aba</tex><br>
3) <tex>abacaba</tex><br>
4) <tex>acaba</tex><br>
5) <tex>ba</tex><br>
6) <tex>bacaba</tex><br>
7) <tex>caba</tex><br>
Значит суффиксный массив для строки <tex>s</tex> равен <tex>suf = \{7, 5, 1, 3, 6, 2, 4\}</tex>
== Применения ==
* Позволяет найти все вхождения образца <tex>p</tex> в строку <tex>s</tex> за время <tex>O(|p| + log(|s|))</tex>
* Позволяет построить массив <tex>lcp</tex> для строки <tex>s</tex> за <tex>O(|s|)</tex>
