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

# | User | Rating |
---|---|---|

1 | tourist | 3882 |

2 | maroonrk | 3539 |

3 | Benq | 3513 |

4 | MiracleFaFa | 3466 |

5 | ksun48 | 3462 |

6 | ecnerwala | 3446 |

7 | slime | 3428 |

8 | Um_nik | 3426 |

9 | jiangly | 3401 |

10 | greenheadstrange | 3393 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 184 |

4 | YouKn0wWho | 182 |

4 | Um_nik | 182 |

6 | antontrygubO_o | 171 |

7 | maroonrk | 169 |

8 | kostka | 165 |

9 | SecondThread | 164 |

9 | errorgorn | 164 |

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

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/24/2022 22:25:35 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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

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?

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

I am using

middleto mean thereflection pointof 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 themiddle. For example, inabcba, themiddleiscand inaaaaaaaa, it isaa. It's easy to see that there areO(N) possiblemiddles(not sure if it's a word, I will usecentersnext time :D). So we can iterate over them and perform a binary search for the longest palindrome, having the currentcenter. That's it. When we fix the lengthL, we can check if it's a palindrome inO(1) using hashing. So,O(N) centers,O(logN) binary search for each of them andO(1) check.thanx sir i got your point really today i learn somethink new thanx once again sir

sir please read my last comment and please clear my dout

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

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

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.

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

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

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

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.

According to yeputons post

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

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:

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