Суффиксный массив

Определение

Определение:

Cуффиксным массивом строки [math]s[1 .. n][/math] называется массив [math]suf[/math] целых чисел от [math]1[/math] до [math]n[/math], такой, что суффикс [math]s[suf[i]..n][/math] — [math]i[/math]-й в лексикографическом порядке среди всех непустых суффиксов строки [math]s[/math].

Пример

[math]s = abacaba[/math]. Суффиксы [math]s[/math] в лексикографическом порядке:
1) [math]a[/math]
2) [math]aba[/math]
3) [math]abacaba[/math]
4) [math]acaba[/math]
5) [math]ba[/math]
6) [math]bacaba[/math]
7) [math]caba[/math]
Значит, суффиксный массив для строки [math]s[/math] равен [math](7, 5, 1, 3, 6, 2, 4)[/math].

Применения

• Позволяет найти все вхождения образца [math]p[/math] в строку [math]s[/math] за время [math]O(|p| + \log(|s|))[/math]
• Позволяет вычислить [math]lcp[/math] (longest common prefix) для всех соседних в лексикографическом порядке суффиксов строки [math]s[/math] за [math]O(|s|)[/math], то есть построить массив [math]lcp[1 .. |s| - 1][/math], где [math]lcp[i][/math] — длина наибольшего общего префикса суффиксов [math]s[suf[i] .. |s|][/math] и [math]s[suf[i + 1] .. |s|][/math].

См. также

• Построение суффиксного массива с помощью стандартных методов сортировки
• Алгоритм поиска подстроки в строке с помощью суффиксного массива

Источники

• Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
• MAXimal :: algo :: Суффиксный массив
• Википедия — Суффиксный массив
• Wikipedia — Suffix array
• Habrahabr — Суффиксный массив — удобная замена суффиксного дерева