Що таке суфіксний масив?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Суфіксний масив (Suffix Array, SA) - це масив індексів усіх суфіксів рядка, відсортованих у лексикографічному порядку. Він дає змогу ефективно шукати підрядки (через двійковий пошук), обчислювати LCP-масив, кількість різних підрядків, найдовші повторювані підрядки, і застосовується у стисненні даних (наприклад, BWT). Будується за O(n log n) (або O(n) просунутими алгоритмами), пошук підрядка - O(m log n).

Детальне пояснення

Що це і навіщо потрібно

Нехай дано рядок S довжини n. Розглянемо всі його суфікси S[i..n-1]. Якщо відсортувати ці суфікси лексикографічно й запам'ятати лише їхні стартові позиції, отримаємо суфіксний масив SA. Маючи SA, можна виконувати швидкий пошук шаблону P в S двійковим пошуком по відсортованих суфіксах, а також розв'язувати безліч рядкових задач ефективніше, ніж наївними методами.

Формальне визначення

Рядок S[0..n-1], зазвичай до нього додають унікальний мінімальний символ-вартовий (sentinel), наприклад '$', якого немає в алфавіті S і який лексикографічно менший за будь-який інший символ. Це спрощує граничні випадки.
Суфіксний масив SA - перестановка індексів [0..n-1], така що суфікси S[SA[0]..], S[SA[1]..], ..., S[SA[n-1]..] впорядковані лексикографічно неспадно.
LCP-масив (Longest Common Prefix) доповнює SA: LCP[i] = довжина найбільшого спільного префікса між суфіксами з індексами SA[i] і SA[i-1] (для i=0 зазвичай 0). Його можна побудувати за O(n) за S і SA (алгоритм Касаі).

Приклад: "banana$"

Розглянемо рядок S = "banana$" (індекси 0..6). Список суфіксів і їхнє сортування:

Індекси і суфікси:
banana$
anana$
nana$
ana$
na$
a$
$

Відсортовані суфікси (лексикографічно):
$
a$
ana$
anana$
banana$
na$
nana$

SA = [6, 5, 3, 1, 0, 4, 2]
LCP = [0, 0, 1, 3, 0, 0, 2]

Тут LCP[3] = 3, бо ana$ і anana$ мають спільний префікс "ana" довжини 3; максимальний LCP дорівнює 3, тому найдовший повторюваний підрядок у "banana" має довжину 3 ("ana").

Застосування

Швидкий пошук підрядка P в S: двійковий пошук по SA за O(m log n), де m - довжина P.
Підрахунок кількості різних підрядків: n(n+1)/2 − sum(LCP).
Пошук найдовшого повторюваного підрядка: max(LCP).
Стиснення даних та індексування: оборотне перетворення Барроуза-Вілера (BWT) будується на базі SA.

Алгоритми побудови (ідея і складність)

Наївний: відсортувати всі суфікси як рядки - O(n^2 log n) за часом, O(n) за пам'яттю, часто занадто повільний.
Подвоєння довжини (prefix-doubling): сортуємо пари рангів (k і k-зсув), подвоюючи k: O(n log n) сортувань; на практиці часто O(n log n). Реалізація проста.
DC3/Skew, SA-IS: лінійний час O(n), складніше в реалізації, використовуються в промислових бібліотеках.
LCP (Касаі): O(n) по вже побудованому SA.

Пошук підрядка через суфіксний масив

Будуємо SA для S (і, опційно, LCP).
Робимо двійковий пошук по масиву суфіксів, порівнюючи P із суфіксом S[SA[mid]..].
Знаходимо діапазон [lo..hi) суфіксів, що починаються з P. Це і є всі входження P в S.

// Побудова суфіксного масиву (prefix-doubling) і LCP (Касаі)
// Важливо: додайте до рядка унікальний мінімальний символ, наприклад '$', якого немає у вихідному рядку.

function buildSuffixArray(s) {
  const n = s.length;
  const sa = Array.from({ length: n }, (_, i) => i);
  // Ранги за символами (використовуємо кодпоінти; для ASCII/UTF-16 достатньо codePointAt)
  let rank = Array.from(s, ch => ch.codePointAt(0));
  let tmp = new Array(n).fill(0);

  for (let k = 1; k < n; k <<= 1) {
    sa.sort((i, j) => {
      if (rank[i] !== rank[j]) return rank[i] - rank[j];
      const ri = i + k < n ? rank[i + k] : -1;
      const rj = j + k < n ? rank[j + k] : -1;
      return ri - rj;
    });

    tmp[sa[0]] = 0;
    for (let i = 1; i < n; i++) {
      const a = sa[i - 1];
      const b = sa[i];
      const same = rank[a] === rank[b]
        && (a + k < n ? rank[a + k] : -1) === (b + k < n ? rank[b + k] : -1);
      tmp[b] = tmp[a] + (same ? 0 : 1);
    }
    for (let i = 0; i < n; i++) rank[i] = tmp[i];
    if (rank[sa[n - 1]] === n - 1) break; // усі ранги унікальні
  }
  return sa;
}

function buildLCP(s, sa) {
  const n = s.length;
  const rank = new Array(n);
  for (let i = 0; i < n; i++) rank[sa[i]] = i;
  const lcp = new Array(n).fill(0);
  let k = 0;
  for (let i = 0; i < n; i++) {
    const r = rank[i];
    if (r === 0) { k = 0; continue; }
    const j = sa[r - 1];
    while (i + k < n && j + k < n && s[i + k] === s[j + k]) k++;
    lcp[r] = k;
    if (k > 0) k--;
  }
  return lcp;
}

// Двійковий пошук підрядка P в S по SA
function findOccurrences(s, sa, pat) {
  const n = s.length;
  const m = pat.length;

  const cmpLower = (idx) => {
    // порівнюємо перші m символів
    const sub = s.slice(idx, idx + m);
    if (sub === pat) return 0;
    return sub < pat ? -1 : 1; // лексикографічне порівняння рядків JS
  };

  // нижня межа (перше місце, де суфікс >= pat-префіксу)
  let lo = 0, hi = n;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    const c = cmpLower(sa[mid]);
    if (c >= 0) hi = mid; else lo = mid + 1;
  }
  const start = lo;

  // верхня межа (перше місце, де суфікс > pat-префіксу)
  const cmpUpper = (idx) => {
    const sub = s.slice(idx, idx + m);
    return sub <= pat ? -1 : 1;
  };
  lo = 0; hi = n;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    const c = cmpUpper(sa[mid]);
    if (c <= 0) lo = mid + 1; else hi = mid;
  }
  const end = lo;

  const res = [];
  for (let i = start; i < end; i++) res.push(sa[i]);
  // Часто зручно повернути відсортовані за позицією входження індекси
  return res.sort((a, b) => a - b);
}

// Демонстрація
const s = "banana$"; // '$' не трапляється в рядку і мінімальний
const sa = buildSuffixArray(s);
const lcp = buildLCP(s, sa);
console.log("SA:", sa);           // [6, 5, 3, 1, 0, 4, 2]
console.log("LCP:", lcp);         // [0, 0, 1, 3, 0, 0, 2]
console.log(findOccurrences(s, sa, "ana")); // [1, 3]

Зв'язок із суфіксним деревом

Суфіксне дерево (Suffix Tree) - потужніша структура з більшим сталим коефіцієнтом пам'яті (часто ~O(n), але з більшим коефіцієнтом).
Суфіксний масив - компактніший, простіше зберігати й серіалізувати; з LCP і RMQ може імітувати багато операцій дерева.

Часті задачі і формули

Кількість різних підрядків рядка S довжини n: n(n+1)/2 − Σ LCP[i]. Інтуїція: усього підрядків n(n+1)/2, спільні префікси між сусідніми суфіксами в SA «дублюють» підрядки і віднімаються сумою LCP.
Найдовший повторюваний підрядок: беремо індекс i з максимальним LCP[i], відповідь - S[SA[i] .. SA[i] + LCP[i] - 1].
Кількість входжень шаблону P: розмір діапазону [lower_bound(P), upper_bound(P)) по SA.

Підводні камені і поради

Завжди додавайте унікальний мінімум-вартовий (наприклад, '$'), щоб коректно обробляти суфікси, уникнути невизначеностей і спростити порівняння на межі рядка.
Стежте за лексикографічним порядком в обраному кодуванні. У JS порівняння рядків - лексикографічне за кодовими одиницями UTF-16; для особливостей Unicode може знадобитися нормалізація.
Подвоєння (prefix-doubling) легко реалізувати, і воно досить швидке на практиці. Для дуже великих даних використовуйте SA-IS/DC3.

Складність (зведення)

Побудова SA: O(n log n) (prefix-doubling) або O(n) (SA-IS/DC3). Пам'ять - O(n).
Побудова LCP (Касаі): O(n) по SA.
Пошук підрядка P: O(m log n) двійковим пошуком; з LCP і RMQ можна прискорювати окремі порівняння.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.