I'm trying to do a problem and i have an idea, but it need to push_front a char to string in O(1) (and for each "push_front" I need to compare two new strings too)!
So...can you tell me how to do it please @@
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3976 |
| 2 | tourist | 3815 |
| 3 | jqdai0815 | 3682 |
| 4 | ksun48 | 3614 |
| 5 | orzdevinwang | 3526 |
| 6 | ecnerwala | 3514 |
| 7 | Benq | 3482 |
| 8 | hos.lyric | 3382 |
| 9 | gamegame | 3374 |
| 10 | heuristica | 3357 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | -is-this-fft- | 165 |
| 3 | Um_nik | 161 |
| 3 | atcoder_official | 161 |
| 5 | djm03178 | 157 |
| 6 | Dominater069 | 156 |
| 7 | adamant | 154 |
| 8 | luogu_official | 152 |
| 9 | awoo | 151 |
| 10 | TheScrasse | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2025 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.01.2025 07:32:09 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by YukatouArimotou (previous revision, new revision, compare).
Auto comment: topic has been updated by YukatouArimotou (previous revision, new revision, compare).
use deque of chars. also there is rope which can insert and delete anywhere in O(logn) but with high constant factor.
can I ask the complexity when comparing 2 deques please?
O(n)
And I forgot, if you use hashing you can compare equality in O(1). I think it's better if you post the problem so people can find a better solution
You can use hashing to insert at the beginning in O(1) too.
Is there any hash template that always AC?
If yes, can I get it please @@
Sorry but the problem is private so I can't show it here.
And...I haven't learned hashing yet @@
Anyway thanks for your help ^^
create array of length 10^6 or whatever and when you gotta do that operation, change the last element first, then the second last, third last, etc etc
but i need to compare 2 strings after each "push_front()" @@
I think you can keep a variable that stores the current position. So like say you have the array [0, 0, 0, 0, 0], your variable stores index 4, and then when you compare, you compare everything from index 5 onwards. You push front an "a", then it becomes [0, 0, 0, 0, "a"], variable becomes 3, and you compare everything from 4 onwards.
Hmmm...It can't help in that problem @@
Anyway thanks for your help ^^
If you're comparing two strings after doing it, the comparison itself will take $$$\mathcal{O}(n)$$$ time anyway, unless the strings are guaranteed to not be too similar for whatever reason. So there is no point of pushing to the front in $$$\mathcal{O}(1)$$$ when it doesn't decrease the time complexity of performing both operations in the worst case.
Ok thank you ^^
Maybe I needa think another idea to solve that problem @@