Сравнение строк с помощью хешей
Материал из Algocode wiki
Версия от 13:41, 24 января 2020; Rationalex (обсуждение | вклад)
Задача
Вам дан набор строк ${S_1, S_2 \dots S_N}$ и Q запросов вида Какая из строк $S_i, S_j$ лексикографически меньше другой?
Решение
Вспомним, что означает лексикографическое меньше для строк: $s$ лексикографически меньше $t$ $iff$ у $s$ и $t$ есть общий префикс длины $i$, и либо $i = |s|$, либо $s[i] < t[i]$.
Будем бинпоиском перебирать длину общего совпадающего префикса, а на равенство префиксы проверять будем с помощью хешей.
Понятно, что функция подходит для бинпоиска, потому что префиксы до некоторого момента совпадают, а потом уже никогда не совпадут.
Итоговая сложность: $O(\underbrace{\sum_{i} |S_i|}_{\text{предподсчёт хешей}} + Q \times log(min(|S_i, S_j|))$