singh1495's blog

By singh1495, history, 5 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

»
5 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.

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

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

    • »
      »
      »
      5 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?

      • »
        »
        »
        »
        5 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

        • »
          »
          »
          »
          »
          5 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.

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

            thanx sir i got your point really today i learn somethink new thanx once again sir

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

            sir please read my last comment and please clear my dout

»
5 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

  • »
    »
    5 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.........

    • »
      »
      »
      5 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.

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

        really thanx a lot i got your point that how i can solve this thanx once again........

»
5 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).

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    why we need to check odd length palindrom and how we can get even length palindrom from above approach please explain....... and also explain its complexity hows it will be O(nlogn)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone send me code according above approach..........

»
5 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

According to yeputons post

Let's break it down. Assume that we have string a0a1a2a3a4a5 (that is n = 6). Then:

S0 = a0
S1 = a0p + a1
S2 = a0p2 + a1p + a2
S3 = a0p3 + a1p2 + a2p + a3
S4 = a0p4 + a1p3 + a2p2 + a3p + a4
S5 = a0p5 + a1p4 + a2p3 + a3p2 + a4p + a5

We want to get hash of a2a3a4, that is, L = 2, R = 4. It should have form of a2p2 + a3p + a4. First, we take S4 as our initial approach:

S4 = a0p4 + a1p3 + a2p2 + a3p + a4

We see that it's almost what we need with several extra terms: a0p4 + a1p3. These terms are hash of substring a0a1000 (I've just took prefix of length five and replaced last three latters with zeros). That is, it's hash of a0a1 multiplied by p3, i.e. S1p3 = (a0p + a1)p3. So, if we subtract these two:

S4 - S1p3 = a0p4 + a1p3 + a2p2 + a3p + a4 - a0p4 - a1p3
S4 - S1p3 = a2p2 + a3p + a4

We get exactly what we wanted.

Does that make more sense now? Please note that there are other approaches with different formulas.

-------------------------------------------------------------------------------------------------------------- question>>

sir if i have string like this a0a1a2a3.......an and n is about 10^5 than p^(n-1) willn't create overflow problem? so is we need to change this equation to this mod is any prime no

S0 = a0 % MOD
S1 = (So.p + a1) % MOD
S2 = (S1p + a2 ) % MOD
S3 =( S2p3 + a3) % MOD
like this.................