Если возможно, как сравнить две строки за O(1)? Заранее спасибо!
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.09.2024 22:16:51 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Если нет никакой дополнительной информации, то на современных компьютерах никак, потому что меньше, чем за O(n) не убедиться, что они различаются.
Есть такая вещь, как хэши. Возможно, помогут.
Стоит, правда, сказать, что там они написаны неоптимально. Например, существует тест, который, если считать хэши подстрок, "валит" решения с любым основанием и модулям вида 2k.
Также там зачем-то предлагают делить на Pk. Это не нужно делать — просто считаем хэши не от префиксов, а от суффиксов. Тогда нам потребуется всего лишь домножить на Pk и выполнить вычитание.
Но с помощью хэшов нельзя сравнивать строки. Поэтому мне нужен оптимальный ответ.
Можно сравнивать 2 захэшированные строки за O(logN)
Ну как сказать. Если хэши совпадают, то с большой вероятностью и сами строки совпадают. Если допускается какая-то вероятность ложно-положительного ответа, то можно сравнивать хэши строк за О(1), при условии что нам изначально даны строки вместе с их хэшами.