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?
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.
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.
Manacher’s algorithm is in principle an online algorithm, this would give something linear.
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.
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.
Ah, thanks. I understand.
http://adilet.org/blog/palindromic-tree/ You can use a Palindrome Tree