given N queries ( N <= 105 ) of 2 types :
initially , string S is empty.
1 ch : push character ch at the end of the string S
2 : return YES if string S is palindrome else return NO
Input
Output
given N queries ( N <= 105 ) of 2 types :
initially , string S is empty.
1 ch : push character ch at the end of the string S
2 : return YES if string S is palindrome else return NO
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
Can you give us a link to the problem, so we can be sure that you are not trying to cheat in a contest?
Actually this problem may not be appear in any OJ.
This problem was came in my mind after the previous contest problem C. Bracket Sequence Deletion
And if you feel like I wanna going to cheat something than you can answer the question after a day or whenever you want.
Thanks.
You can simply add characters to string using .push_back function and check if it is palindrome by looping to size/2 and check if s[i] == s[n-i-1]
Sorry I forgot that it will lead to TLE :)
Checking after each query will leads to TLE :(
hashing?
You can simply hash the initial string and its reversed version. After every push_back you can easily recalculate both hashes. It would be something like reversedHash += polynomBase ^ {len(s)}, straightHash = straightHash * polynomBase + getCharHash(newCharacter). To check if the string is palindrome, you only need to know, if reversed hash is equal to usual one.
use Palindromic Tree, if the len of the Last Status equal to n that the string S is palindrome. Palindromic Tree is $$$O(n)$$$
Solve offline
For the text, you can find, if every prefix is palindrome or not by Manacher's algorithm O(N)