Суффиксный массив
Содержание
Определение
Определение: |
Cуффиксным массивом строки | называется массив целых чисел от до , такой, что суффикс — -й в лексикографическом порядке среди всех непустых суффиксов строки .
Пример
1)
2)
3)
4)
5)
6)
7)
Значит суффиксный массив для строки равен
Применения
- Позволяет найти все вхождения образца в строку за время
- Позволяет вычислить (longest common prefix) для всех соседних в лексикографическом порядке суффиксов строки за , то есть построить массив , где — длина наибольшего общего префикса суффиксов и .
Литература
- Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.