Сравнение строк с помощью хешей: различия между версиями
Материал из Algocode wiki
(не показана 1 промежуточная версия этого же участника) | |||
Строка 5: | Строка 5: | ||
=== Решение === | === Решение === | ||
− | Вспомним, что означает лексикографическое меньше для строк: $s$ лексикографически меньше $t$ $iff$ у $s$ и $t$ есть общий префикс длины $i$, и либо $i = |s|$, либо $s[i] < t[i]$. | + | Вспомним, что означает лексикографическое меньше для строк: $s$ лексикографически меньше $t$ $\iff$ у $s$ и $t$ есть общий префикс длины $i$, и либо $i = |s|$, либо $s[i] < t[i]$. |
Будем бинпоиском перебирать длину общего совпадающего префикса, а на равенство префиксы проверять будем с помощью [[Полиномиальное хеширование строк|хешей]]. | Будем бинпоиском перебирать длину общего совпадающего префикса, а на равенство префиксы проверять будем с помощью [[Полиномиальное хеширование строк|хешей]]. | ||
Строка 12: | Строка 12: | ||
Итоговая сложность: $O(\underbrace{\sum_{i} |S_i|}_{\text{предподсчёт хешей}} + Q \times log(min(|S_i, S_j|))$ | Итоговая сложность: $O(\underbrace{\sum_{i} |S_i|}_{\text{предподсчёт хешей}} + Q \times log(min(|S_i, S_j|))$ | ||
+ | |||
+ | {{Автор|Александр Гришутин|rationalex}} |
Текущая версия на 13:42, 24 января 2020
Задача
Вам дан набор строк ${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