Информатика · учебный маршрут
Сортировки и сравнение строк
Проследите перестановки элементов и состояние алгоритма. Сравните способы работы с порядком и с общими фрагментами строк.

Чему научитесь
Различать шаг алгоритма, его инвариант и итог; проверять стоимость исправления строки.
Что пригодится
- Индексы массива
- Цикл и сравнение значений
10 тем по порядку
Читайте объяснение или сразу переходите к заданию
- Практика
Сортировка вставками: как элемент находит место в готовом префиксе
Сортировка вставками на небольшом списке: готовый префикс, сдвиги больших элементов и сохранение порядка одинаковых значений.
- Практика
Слияние отсортированных частей: два указателя и стабильность
Слияние двух готовых массивов: сравнение первых оставшихся элементов, обработка хвоста и правило стабильности при равенстве.
- Практика
Разбиение около опорного: что гарантирует один шаг быстрой сортировки
Что делает разбиение около опорного элемента: области меньше, равно и больше, их инварианты и границы обещания одного шага.
- Практика
Сортировка подсчётом: диапазон значений важнее числа разрядов
Сортировка подсчётом: частоты целых ключей, сдвиг отрицательного диапазона и отличие числа значений от ширины диапазона.
- Практика
Поразрядная сортировка: зачем каждому проходу стабильность
LSD-сортировка по разрядам: проход от единиц к старшим цифрам, сохранение прежнего порядка и границы числовой модели.
- Практика
Порядковая статистика: найти k-й элемент без полной сортировки
Поиск k-го наименьшего элемента: локальный ранг после разбиения, повторяющиеся значения и выбор только нужной области.
- Практика
Префикс-функция: как искать границу совпавшего фрагмента
Префикс-функция строки: собственная граница, суффикс обработанного префикса и переход к более короткому совпадению.
- Практика
Z-функция строки: длины совпадения с её началом
Z-функция без путаницы с префикс-функцией: совпадение от текущей позиции, правая граница известного блока и длина результата.
- Практика
Скользящий хеш: быстро сравнить кандидатов и проверить совпадение
Скользящий полиномиальный хеш: два обновления окна, согласование степеней, нормализация отрицательного остатка и проверка прямым подсчётом.
- Практика
Расстояние редактирования: вставить, удалить или заменить символ
Как получается расстояние Левенштейна: префиксы строк, вставка, удаление, замена и проверка минимального пути.
Как заниматься
Нужно проходить все темы подряд?
Последовательность помогает связать понятия, но можно открыть любую тему. Если задача уже знакома, начните с практики: ответ сопровождается объяснением.
Что делать, если ответ оказался неверным?
Прочитайте объяснение к ответу и сопоставьте его с разобранным примером. Найдите первый шаг, где ваше рассуждение отличается, затем попробуйте решить задание ещё раз.