aman_naughty's blog

Number of pallindromic prefixes efficiently??
By aman_naughty, history, 5 years ago, In English

Can someone suggest some method to count the number of prefixes of a given string which are also palindromes? It would be even helpful if I can get a boolean array of the length of string where a true denotes that a prefix up to this index is a palindrome.

Right now I have a simple 2d dp approach where dp[i][j] is true if string i to j is a palindrome, but this is O(n2). Is there some O(n) or O(nlog(n)) method thankyou.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

One possible way to do it is hashing. Basically you can build hash "table"s on string itself and its reverse(you can do it without reverse string actually). Then iterate over all indices and check if the hash of prefix and its reverse are same or not. Of course, we can get hash of a range in O(1) if properly implemented.

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

    I believe you are suggesting something similar to Rabin-Karp algorithm but it does not always guarantee a match and we have to check the strings character-wise once hash value matches right.

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

      It's a probabilistic algorithm. The key to those is to simply try acknowledge the probability of error and to make it as small as possible.

      Suppose we calculate a "forwards-hash" and a "backwards-hash" for each prefix, let's say modulo $$$10^9$$$ (actually you want this to be a prime number but I took a round number for convenience). We can regard the hashes as "random". The prefix can only be a palindrome if the forwards-hash and backwards-hash are equal. But there's also a $$$\approx 10^{-9}$$$ chance that they are equal by coincidence. That's actually fairly big, if you have a string with length $$$10^5$$$ and no palindromic prefixes, there's a $$$(1 - 10^{-9})^{10^5} \approx 0.9999$$$ chance that you make no errors. If there are 100 test cases, that gives a $$$(1 - 10^{-9})^{10^7} \approx 0.99$$$ chance that you make no errors.

      But if you don't like those odds, make the hashes modulo $$$10^{18}$$$ instead, or calculate two different hashes modulo $$$10^9$$$. Now the probability that you make no errors is so close to 1 that you're not going to see it fail in your lifetime.

      So yes, if you wanted to be sure you have to check the characters. But if you're fine with being sure with $$$10^{-11}$$$ chance of error, it's not necessary.

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

it is possible to compute this in $$$\mathcal{O}(n)$$$ with the help of manacher's algorithm

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

You can concatenate given string with reversed string. Than just use z function.

→ Reply