TooMuchPainTheseDays's blog

NEED HELP : Palindrome Problem
By TooMuchPainTheseDays, 2 years ago, In English

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
  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

hashing?

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Solve offline

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

→ Reply