### singh1495's blog

By singh1495, history, 5 years ago,

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

• +9

 » 5 years ago, # |   +5 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, # ^ |   0 can u explain me in more detail please.............
•  » » » 5 years ago, # ^ |   +5 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, # ^ |   0 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 →   0 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, # ^ |   0 thanx sir i got your point really today i learn somethink new thanx once again sir
•  » » » » » » 5 years ago, # ^ |   0 sir please read my last comment and please clear my dout
 » 5 years ago, # |   0 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, # ^ |   0 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 →   0 http://codeforces.com/blog/entry/21452Some comments in that blog explain how to find hash of substring in O(1), precalculation O(N) and memory O(N). Look thereFirst 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, # ^ |   0 really thanx a lot i got your point that how i can solve this thanx once again........
 » 5 years ago, # | ← Rev. 2 →   +11 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 →   0 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, # |   0 can someone send me code according above approach..........
 » 5 years ago, # |   0 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, # |   0 According to yeputons postLet'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 + a5We 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 + a4We 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 + a4We 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.................