proofbycontradiction's blog

Identifying Palindromes Online
By proofbycontradiction, history, 6 years ago, In English

This is a problem that I've been thinking of for quite a while.

You start with the empty string. There will be $$$q$$$ queries. Each query will append a character to the string. You have to answer if the new string is a palindrome.

  • "" — add A ----> "A" = True
  • "A" — add B ---> "AB" = False
  • "AB — add A ---> "ABA" = True
  • .... and so on for $$$q$$$ steps.

Is there an efficient (better than $$$O(q^2)$$$) online solution for this problem?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 5   Vote: I like it +13 Vote: I do not like it

Since each query only adds a character to the end of the string, I think you can maintain a segment tree. Each node of the tree can store the two hash values of the respective substring (one for the substring and one for its reverse version). If my math is right, I can easily implement the operators get and update on the tree and solve this problem in $$$O(q\log{q})$$$.

I think this problem can be solve in $$$O(q)$$$ by maintaining two hash values $$$H_1$$$ and $$$H_2$$$.

Let $$$x$$$ be the value of the new character, $$$b$$$ be the base, and $$$l$$$ is the length of the string, then for each query, $$$H_1 = H_1 \times b + x$$$ (append to the end) and $$$H_2 = H_1 + x \times b^l$$$ (append to the front). If $$$H_1 = H_2$$$, then print True, otherwise print False.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. Your solution also allows me to answer if a substring is a palindrome. And if we include persistence, then I can fork my string as well.

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

Manacher’s algorithm is in principle an online algorithm, this would give something linear.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I remembered that you could use it to count the palindromes in a string, but I've forgotten how it works. I'll look it up now.

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

you can use polynomial hashing. If cou have the hash of a string $$$s$$$ you can easily calculate the hash of $$$s+'a'$$$ and $$$'a'+s$$$. Just update the hash of the string and the reversed string and check if they are equal to check if its a palindrome.

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

http://adilet.org/blog/palindromic-tree/ You can use a Palindrome Tree

→ Reply