Блог пользователя TooMuchPainTheseDays

NEED HELP : Palindrome Problem
Автор TooMuchPainTheseDays, 3 года назад, По-английски

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
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you give us a link to the problem, so we can be sure that you are not trying to cheat in a contest?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
»
3 года назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 :)

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

hashing?

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

use Palindromic Tree, if the len of the Last Status equal to n that the string S is palindrome. Palindromic Tree is $$$O(n)$$$

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Solve offline

For the text, you can find, if every prefix is palindrome or not by Manacher's algorithm O(N)

→ Ответить