редакторы текста

Статьи

DS Структура данных Связный список Узлы со ссылками на соседей: вставка и удаление у известного узла за O(1), путь к k-му — k шагов. O(1) у известного узла 2 задачи DS Структура данных Стек и очередь Стек: последним пришёл — первым ушёл. Очередь: первым пришёл — первым ушёл. Каждая операция — O(1). O(1) на push и pop, enqueue и dequeue 2 задачи DS Структура данных Верёвка Текст кусками в листьях дерева: вставка и удаление в середине — путь к листу и один кусок; номер строки — по счётчикам в узлах. O(log n + C) на вставку, удаление, доступ 1 задача DS Структура данных Бор (префиксное дерево) Слова с общим началом идут общим путём: поиск слова и всех продолжений — за длину запроса. O(L) на вставку и поиск слова длины L 2 задачи STR Алгоритм Наивный поиск подстроки Образец прикладывают к каждой позиции текста: n · m сравнений в худшем случае, около n — на обычном тексте. O(n · m) 2 задачи STR Алгоритм Z-функция Сколько букв от каждой позиции совпадает с началом строки — за O(n); поиск, периоды и повторы подряд. O(n) 2 задачи STR Алгоритм Бойер — Мур Сравнивает справа налево и перепрыгивает буквы: на длинных образцах читает лишь малую часть текста. O(n + m) 2 задачи STR Алгоритм Diff Майерса Кратчайший сценарий удалений и вставок строк за O((N + M) · D): волны по числу правок. Так работает git diff. O((N + M) · D) 1 задача DP Алгоритм Наибольшая общая подпоследовательность Самая длинная цепочка, общая двум последовательностям: таблица m × n, путь назад, Хиршберг. O(m · n) 2 задачи DP Алгоритм Красивый перенос строк Жадный перенос против всего абзаца сразу: кратчайший путь по местам разрыва, как в TeX. O(n·L) 2 задачи SYS Структура данных CRDT Данные, копии которых правят независимо и сливают в любом порядке: счётчики, множества, текст.

O(1) на операцию у счётчика и множества; вставка в текст — O(1) в среднем

2 задачи

Задачи

Скобки в рукописи Журнал нажатий Подсказки по роману Словарное разнообразие Текст без пробелов Ровный заголовок Ровный правый край Слить правки без сервера Все версии текста Фраза дважды

Часто рядом

классика 9 собеседования 5 в проде 5 поиск в тексте 4 амортизация 3 динамика 3 связный список 2 массив 2 операционные системы 2 дерево 2 поиск 2 биоинформатика 2