singh1495's blog

hashing technique
By singh1495, history, 7 years ago, In English

can someone tell me how we can find longest palindrom substring in O(nlogn) complexity using hashing thanx in advance.........

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

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

Fix some element which will be in the middle (or some two consecutive equal elements which will be in the middle). Now do a binary search for the longest palindromic substring having this/these element/elements in the middle.

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

    can u explain me in more detail please.............

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

      Can you ask a more specific question? Like which is the last thing you understood from my comment? I can write a longer comment saying nothing more than the previous one. BTW, your comments below really make me wonder, what's your knowledge about hashing?

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

        but sir there will be n-2 element in the middle and if i find longest palindromic substring by making any point as a middle point than hows its complexity will be O(nlogn) so sir please explain me i m new i donot have any idea about it that how i can solve this usinh hashing

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

          I am using middle to mean the reflection point of the palindrome i.e. the place where after splitting, we receive two identical parts. So there are only 1 (in case of odd length) or 2 (in case of even length) elements in the middle. For example, in abcba, the middle is c and in aaaaaaaa, it is aa. It's easy to see that there are O(N) possible middles (not sure if it's a word, I will use centers next time :D). So we can iterate over them and perform a binary search for the longest palindrome, having the current center. That's it. When we fix the length L, we can check if it's a palindrome in O(1) using hashing. So, O(N) centers, O(logN) binary search for each of them and O(1) check.

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

If you wanna know if there is some palindrome of size T in a string you can do the follow, do hash for every interval of size T in the normal string and in the reverse string, if the hash of some interval is equal in both cases, this means that the interval is a palindrome, you can do this in O(n) with rabin karp.

Now, realize that if you there is a palindrome of size X in the string there is a palindrome of size X-2, X-4, ..., so you can do binary search on the size of the palindrome for odd sizes and even sizes, so the final complexity will be O(n log n). Sorryy by the poor English

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

    but how it will be O(nlogn) because according to your approach we first find hash of every substring of size x in both string and reverse string so total substring of size 1 = (n-1) + (n-1) (due to reverse string) "" "" "" "" "" "" size2 = (n-2) + (n-2)

    like this 2(n-1) + 2(n-2) + ...........+ 1 and addtinal O(logn) for binary search... so it will be O(n^2logn) so how it can be O(nlogn)........ please help me.........

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

      http://codeforces.com/blog/entry/21452

      Some comments in that blog explain how to find hash of substring in O(1), precalculation O(N) and memory O(N). Look there

      First of all, put a delimiter character ('#' for example) before every character in the string and after last character (as explained in other comment below.). Do same for the reverse string. Now precalculate hash array for normal string and reverse string.

      Then, fix a position i and binary search for largest value v, such that Hash of substring (i — v, i — 1) equals Reverse Hash of substring (i + 1, i + v). Binary search takes O(logN), and at each step we check in O(1) if two substring are equals. So log(N) for each position, O(NlogN) total.

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

First put a delimiter char (maybe '#') before every char in the string and after the last char, this will be like, if S = "abbaca" then will convert it to S = "#a#b#b#a#c#a#".

Then in the new string you can do a binary search on the palindrome length, and this length will always be odd, if you have palindrome with len = 9 then you have also palindrome with len 7, 5, 3, 1. and you don't have to worry about even or odd palindromes because you now only solving for odd and the result will be floor(len/2).

For a fixed length (from the BS) you can do a check in O(N) if there is a palindrome with this length or not using hashing, by hashing 2 windows with this length one foreword and one backward and check if they are equals or not, and slide to the next char in O(1).

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

I know that u're looking for help in hashing in this task but fyi it's worth to mention there's linear Manaker's algorithm.

→ Reply