{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Короткий ответ" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Суффиксный массив (Suffix Array, SA) — это массив индексов всех суффиксов строки, отсортированных в лексикографическом порядке. Он позволяет эффективно искать подстроки (через бинарный поиск), вычислять LCP-массив, количество различных подстрок, самые длинные повторяющиеся подстроки и применяется в сжатии данных (например, BWT). Строится за O(n log n) (или O(n) продвинутыми алгоритмами), поиск подстроки — O(m log n)." } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Подробное объяснение" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Что это и зачем нужно" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Пусть дана строка S длины n. Рассмотрим все её суффиксы S[i..n-1]. Если мы отсортируем эти суффиксы лексикографически и запомним только их стартовые позиции, получим суффиксный массив SA. Имея SA, можно выполнять быстрый поиск шаблона P в S бинарным поиском по отсортированным суффиксам, а также решать множество строковых задач более эффективно, чем с наивными методами." } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Формальное определение" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Строка S[0..n-1], обычно к ней добавляют уникальный минимальный символ-страж (sentinel), например '$', которого нет в алфавите S и который лексикографически меньше любого другого символа. Это упрощает граничные случаи." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Суффиксный массив SA — перестановка индексов [0..n-1], такая что суффиксы S[SA[0]..], S[SA[1]..], ..., S[SA[n-1]..] упорядочены лексикографически неубывающе." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "LCP-массив (Longest Common Prefix) дополняет SA: LCP[i] = длина наибольшего общего префикса между суффиксами с индексами SA[i] и SA[i-1] (для i=0 обычно 0). Его можно построить за O(n) по S и SA (алгоритм Касаи)." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Пример: \"banana$\"" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Рассмотрим строку S = \"banana$\" (индексы 0..6). Список суффиксов и их сортировка:" } ] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "Индексы и суффиксы:\n0: banana$\n1: anana$\n2: nana$\n3: ana$\n4: na$\n5: a$\n6: $\n\nОтсортированные суффиксы (лексикографически):\n6: $\n5: a$\n3: ana$\n1: anana$\n0: banana$\n4: na$\n2: nana$\n\nSA = [6, 5, 3, 1, 0, 4, 2]\nLCP = [0, 0, 1, 3, 0, 0, 2]" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Здесь LCP[3] = 3, потому что ana$ и anana$ имеют общий префикс \"ana\" длины 3; максимальный LCP равен 3 → самая длинная повторяющаяся подстрока в \"banana\" имеет длину 3 (\"ana\")." } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Применения" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Быстрый поиск подстроки P в S: бинарный поиск по SA за O(m log n), где m — длина P." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Подсчет количества различных подстрок: n(n+1)/2 − sum(LCP)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Поиск самой длинной повторяющейся подстроки: max(LCP)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Сжатие данных и индексирование: обратимое преобразование Барроуза–Уилера (BWT) строится на базе SA." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Алгоритмы построения (идея и сложность)" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Наивный: отсортировать все суффиксы как строки — O(n^2 log n) по времени, O(n) по памяти, часто слишком медленный." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Дублирование длины (prefix-doubling): сортируем пары рангов (k и k-сдвиг), удваивая k: O(n log n) сортировок; на практике часто O(n log n). Реализация проста." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "DC3/Skew, SA-IS: линейное время O(n), сложнее в реализации, используются в промышленных библиотеках." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "LCP (Касаи): O(n) по уже построенному SA." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Поиск подстроки через суффиксный массив" } ] }, { "type": "orderedList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Строим SA для S (и, опционально, LCP)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Делаем бинарный поиск по массиву суффиксов, сравнивая P с суффиксом S[SA[mid]..]." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Находим диапазон [lo..hi) суффиксов, начинающихся с P. Это и есть все вхождения P в S." } ] } ] } ] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "// Построение суффиксного массива (prefix-doubling) и LCP (Касаи)\n// Важно: добавьте к строке уникальный минимальный символ, например '$', которого нет в исходной строке.\n\nfunction buildSuffixArray(s) {\n const n = s.length;\n const sa = Array.from({ length: n }, (_, i) => i);\n // Ранги по символам (используем кодпоинты; для ASCII/UTF-16 достаточно codePointAt)\n let rank = Array.from(s, ch => ch.codePointAt(0));\n let tmp = new Array(n).fill(0);\n\n for (let k = 1; k < n; k <<= 1) {\n sa.sort((i, j) => {\n if (rank[i] !== rank[j]) return rank[i] - rank[j];\n const ri = i + k < n ? rank[i + k] : -1;\n const rj = j + k < n ? rank[j + k] : -1;\n return ri - rj;\n });\n\n tmp[sa[0]] = 0;\n for (let i = 1; i < n; i++) {\n const a = sa[i - 1];\n const b = sa[i];\n const same = rank[a] === rank[b]\n && (a + k < n ? rank[a + k] : -1) === (b + k < n ? rank[b + k] : -1);\n tmp[b] = tmp[a] + (same ? 0 : 1);\n }\n for (let i = 0; i < n; i++) rank[i] = tmp[i];\n if (rank[sa[n - 1]] === n - 1) break; // все ранги уникальны\n }\n return sa;\n}\n\nfunction buildLCP(s, sa) {\n const n = s.length;\n const rank = new Array(n);\n for (let i = 0; i < n; i++) rank[sa[i]] = i;\n const lcp = new Array(n).fill(0);\n let k = 0;\n for (let i = 0; i < n; i++) {\n const r = rank[i];\n if (r === 0) { k = 0; continue; }\n const j = sa[r - 1];\n while (i + k < n && j + k < n && s[i + k] === s[j + k]) k++;\n lcp[r] = k;\n if (k > 0) k--;\n }\n return lcp;\n}\n\n// Бинарный поиск подстроки P в S по SA\nfunction findOccurrences(s, sa, pat) {\n const n = s.length;\n const m = pat.length;\n\n const cmpLower = (idx) => {\n // сравниваем первые m символов\n const sub = s.slice(idx, idx + m);\n if (sub === pat) return 0;\n return sub < pat ? -1 : 1; // лексикографическое сравнение строк JS\n };\n\n // нижняя граница (первое место, где суффикс >= pat-префиксу)\n let lo = 0, hi = n;\n while (lo < hi) {\n const mid = (lo + hi) >> 1;\n const c = cmpLower(sa[mid]);\n if (c >= 0) hi = mid; else lo = mid + 1;\n }\n const start = lo;\n\n // верхняя граница (первое место, где суффикс > pat-префиксу)\n const cmpUpper = (idx) => {\n const sub = s.slice(idx, idx + m);\n return sub <= pat ? -1 : 1;\n };\n lo = 0; hi = n;\n while (lo < hi) {\n const mid = (lo + hi) >> 1;\n const c = cmpUpper(sa[mid]);\n if (c <= 0) lo = mid + 1; else hi = mid;\n }\n const end = lo;\n\n const res = [];\n for (let i = start; i < end; i++) res.push(sa[i]);\n // Часто удобно вернуть отсортированные по позиции вхождения индексы\n return res.sort((a, b) => a - b);\n}\n\n// Демонстрация\nconst s = \"banana$\"; // '$' не встречается в строке и минимален\nconst sa = buildSuffixArray(s);\nconst lcp = buildLCP(s, sa);\nconsole.log(\"SA:\", sa); // [6, 5, 3, 1, 0, 4, 2]\nconsole.log(\"LCP:\", lcp); // [0, 0, 1, 3, 0, 0, 2]\nconsole.log(findOccurrences(s, sa, \"ana\")); // [1, 3]" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Связь с суффиксным деревом" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Суффиксное дерево (Suffix Tree) — более мощная структура с большим постоянным фактором памяти (часто ~O(n) но с большим коэффициентом)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Суффиксный массив — компактнее, проще хранить и сериализовать; с LCP и RMQ может эмулировать многие операции дерева." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Частые задачи и формулы" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Количество различных подстрок строки S длины n: n(n+1)/2 − Σ LCP[i]. Интуиция: всего подстрок n(n+1)/2, общие префиксы между соседними суффиксами в SA «дублируют» подстроки и вычитаются суммой LCP." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Самая длинная повторяющаяся подстрока: берём индекс i с максимальным LCP[i], ответ — S[SA[i] .. SA[i] + LCP[i] - 1]." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Количество вхождений шаблона P: размер диапазона [lower_bound(P), upper_bound(P)) по SA." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Подводные камни и советы" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Всегда добавляйте уникальный минимум-страж (например, '$'), чтобы корректно обрабатывать суффиксы, избежать неопределённостей и упростить сравнения на границе строки." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Следите за лексикографическим порядком в выбранной кодировке. В JS сравнение строк — лексикографическое по кодовым единицам UTF-16; для Unicode-особенностей может понадобиться нормализация." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Дублирование (prefix-doubling) легко реализовать и достаточно быстро на практике. Для очень больших данных используйте SA-IS/DC3." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Сложность (сводка)" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Построение SA: O(n log n) (prefix-doubling) или O(n) (SA-IS/DC3). Память — O(n)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Построение LCP (Касаи): O(n) по SA." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Поиск подстроки P: O(m log n) бинарным поиском; с LCP и RMQ можно ускорять отдельные сравнения." } ] } ] } ] } ] }

Что такое суффиксный массив?

Комментарии