Сравнение строк с помощью хешей

Задача

Вам дан набор строк ${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|))$

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex