Longest Palindromic Substring Manacher's Algorithm

hello friends my name is too sharp and today I am going to talk about how to find the longest palindromic substring in linear time using monikers algorithm so here you are given a string and you have to find the longest palindromic substring in this string so there are many palindromic substring in this string for example this this or this with Center X so the question is to find the longest palindromic substring so the longest minute of substring here is this with Center is B and the length is nine so there are many algorithms to solve this in over n square time but today we are going to consider the many codes and guard them which solves it in off n time also for keeping the video simple I am only going to consider the order length palindromes but I will show later on how you without losing generality you can also solve it for even length palindrome so in the next section let's see how medicals algorithm works the first thing I do is take a check very array of the same size as my input array so then I start expanding around a so there is nothing to expand around a so the length of the longest palindrome with center a will be of 1 then we go to B again we are just dealing with the odd length palindromes so we don't have to look for the palindrome between a and B so we can directly jump to B and this is for simplicity purpose so we go to be the longest palindrome around central B will be of length 3 then we go to a the longest palindrome around a will be of length 1 then we go to X the longest palindrome around Center X will be 3 5 and then 7 so 7 at this point the question is what should be the next Center so we have already explored till this point so the question is what should be the next century can they say this X will be the next Center no if we do that we miss the palindrome around B which is the longest palindrome by the droving substring in this string so can we go to a and then go to B and then go to a and like Explorer on a and then Explorer on B and then explore around a we can do that but the problem is then it becomes a orphan for n square time algorithm and cannot be done in a linear time so how do we effectively pick the next Center so to pick the next entry the idea is that we should pick such a guys the next Center such that the palindrome around it expands till the right edge of the characters we have explored till not so palindrome around a expands just till a and doesn't go to the right edge which is 6 so this guy cannot be the cannot be the next Center because about anybody room around a will be contained around this bigger palindrome so this will never give me a longest palindrome what about B the palindrome are on be at least expands till Lindemann on B is here so it at least expands to the right edge of the current current Center which is this guy so B can be the next candidate and what about a again palindrome around a at least expands to the right edge of the current Center palindrome which is X so a also can be the next candidate but out of BN a V gives me the longest palindrome which is at least of length 3 while it gives me of length 1 so my next candidate will be B again why we work why this works is because if if my palindrome around this Center expands at least to the right edge of the current palindrome of the current palindrome the thing is there is a possibility that it can expand even more since it's not contained in the bigger palindrome which means that there is a possibility it can expand more if you look at B it here it expands to the right edge and then it can continue to expand more and probably might and can give me a bigger length palindrome which is why the next century will be B so now the question is how do we know that which Center has a palindrome which expands to the right edge and then we can go to a and see does the palindrome around a expand to the right of the palindrome water under X and then we go to B and then we go away but if you do that again this algorithm doesn't stay linear so what we do is we use information we have calculated till now so if you if you look at X we know that there is a palindrome from 0 to 6 so we know that this side should be the mirror of this side so we have already calculated what is the longest palindromes around on this sides 1 3 1 so what I can say is that the longest pendulum on the other side will at least be of these lengths so this a is a mirror of this edge so the longest palindrome here will at least be of length 1 the longest part number on B will at least be of length 3 the longest palindrome are on this a will at least be of length 1 now I have this information and so now I can make a call that which will be my next Center and that will be this guy because the palindrome are on this guy at least expands till the right edge of the current palindrome I have found so this is how B will be my next Center let's expand our own schedule B so we know that the palindrome under center B was at least of length 3 so there is no reason to look at these two guys that we start comparing directly from here and here so this is same then this is same and then this is same and these guys are different so the palindrome around Center B will be of length 9 so at this point at this point our question is what should be the next Center so let's see again so we go back here we copy this number here the saying that palliative or this will at least be of length 1 or more then we go here can you copy this 7 here and the answer is no why the palindrome around this X was of length the palindrome around this X was expanding from this point to this point and the palindrome around this B is expanding from this be - this be so the Pauline devor this X goes beyond the left edge of of this car my current palindrome so I there is no guarantee that the pendulum on the other side will be of length seven so the island over on this other side will we know that will be till this edge and this point so the size will be five instead of seven also then we go to a and this will be of length one and then we go to be the same is for B the palindrome around this B was expanding from this to this and this is beyond the left edge of my current bedroom under B so I cannot say that the palindrome that this B will be of length three so this will be of length one so another question is who should I pick as my next century should I pick five as my next Center I'm in this X is my next Center and the answer is no there is no reason to pick this guy's the next central and let's understand why if if they pick the reason I'm saying there is no reason to pick X as a neck center is because there is no way it will it will grow beyond the current set current length of Y why I mean you might say that the current length is five what if this cat true was a and what if there was another X and another and another B after this it's a valid point the point is if this cat arose in you would have already expanded under this center so only reason this gets talked here was because this character was not if we matched to this point and these two guys were different so we stopped here so only reason we stopped was because this guy was not a if this guy was a we would have continued explode under this central D and we were not stopped and the dynamics would be different the values would be different so since this is not a this is B then the reason we stopped and since this is B or any character which is not a there is no way Earth's parameter X will expand more this palindrome is totally contained under this so let's look at this guy this guy here also has the same problem there is no way the only reason we stopped for this B was because this a was not this a and there is no way we can expand more in this direction because I mean there is no way this guy would be a and expand more here because if this was a we would have explored continue to explore and under this Center so since this is not a be stopped here to do so this is B so there is no way we'll have a palindrome bigger than this size so the next Center will be this guy which is B last B and the palindrome around in terms of length 1 so finally we just write rate through this input array and 9 will be our answer in the next section let's look at another bigger example and let's try to understand this concept again let's work through this example to clearly understand their manicures algorithm so we have four cases here case one is do not pick a character as a new center if the palindrome under it is totally contained under the current palindrome the case number two is is a current palindrome expands all the way to the end of the input there is no reason to proceed and we should break out of the while loop case three is pick a character as a center if it expands all the way to the right edge and it's mirror palindrome expands all the way to the left edge basically it's a proper suffix of the current palindrome a proper prefix of the current palindrome and do not take a character as a new center if it expands all the way to the right edge but it's but it's mirror padded room expands beyond the left edge basically it's not a proper prefix so let's apply all these four cases on this example so what it it has I took a new array of the same size and again we are only going to deal with the odd length parent room for the purposes of centricity so we start with a the palindrome here is of length 1 we start with B the palindrome here is of length 3 then we go to a the palindrome here is of length 1 if we go to X so this is same this is same and this is same so the palindrome here is of length 7 so at this point where we have to pick the new Center so we work backwards we go to this one and copy it here since the palindrome here is of length one for this a it will be totally contained under the current palindrome which is off which is going from this a to this a so this is a case number one so this guy will not be the new Center then you go to here and be Papa this guy here so palindrome this is now case three the palindrome with Center B expands all the way to the right edge and it's mirror expands all the way to the left edge it's a proper prefix of the current palindrome so B is our new center so we expand around B again we know that B at least has a palindrome of length 3 so we start comparing this X with this exit say it's safe and it's same and then they are different so the palindrome here is of length 9 so then we have to pick the next Center again we start working backwards from 9 so one copies here this is a case 1 there is no way this this guy is totally contained under the current palindrome going from B to B this 7 so the palindrome at center X is from was from a to a so it was the pile in right-center X was going beyond the current palindrome so it's not a proper prefix so we hit a case 4 so X should not be the new Center so we will put the value 5 which is the maximum palindrome which is the maximum size pareto with the center X but this guy will not be the new Center as because it's a case number 4 so then we go here this is totally contained so it's a case number 1 then we go here again this B has a palindrome which is goes beyond the left center of the palindrome under center B so again this B should not be the new central but we'll just put the value here of 1 which is a total sense palindrome under central B so next center will be Y since none of the other guys match the criteria so we expand around why this is saying this is same this is same this is same this is same so the length here is eleven three five seven nine eleven so again we work backwards so we copied this guy here this is case one so this is totally contained under this palindrome this is case one this guy five so palindrome with center X was here to here and our current palindrome is from here to here so parental minor sin 2x is a proper prefix of this guy so this guy here will go till all the way to the right edge and so this guy will be our new center because it's a case number three so this guy becomes over newscenter5 so when I go here I already know that there's a pattern tomb of length five so I start working I five five factors are already taken care of sigh compare them they are same and they are same so seven and nine and now we hit the end of the input so we hit case number two so that's it we'll stop processing at this point because all the valid rules are after this will be a smaller size so at this point we just i traits which is very fine for the maximum number which is 11 so the palindrome under center y will be of length 11 and that'll be the longest palindromic substring for this string the run time complexity will be two of em so basically oh and in the next section let's see how do we deal with the even length palindromes so let's see how we will deal with the even length palindrome so here the maximum length palindrome will be of length four and the center is between this two is so I got this technique from the leet code which and it makes coding really easy so what we do is we take a new input array of size 2 n plus 1 so this is 11 and what we do is we put a special Sentinel characters between all the these characters so let's say dollar was that character so we say dollar a dollar B dollar a dollar the dollar B and then dollar so now all we have to do is apply our regular algorithm which we just discussed before on this input string and then that will give you the longest palindrome and then once you get the longest palindrome all if you have to do is divide it by two so in this case the longest palindrome will be from here to here and it's length will be three five seven nine once you get this value all you do is divide it by 2 and get 4 which is the length of the longest palindrome from V to V so again this doesn't affect the runtime complexity because we are still dealing in and so even with this there are time complexity will be O of n so this is all I have to talk about man occurs algorithm today I would ask my viewers to LIKE this video share this video comment on this video check out my github link and also like my Facebook page the code is in the description section of this video the link to the code is in the description section of this video alright thanks again for watching this video

Channel: Tushar Roy - Coding Made Simple

Views: 263,866

Keywords: Longest Palindromic Substring, Manacher's algorithm

Id: V-sEwsca1ak

Length: 16min 45sec (1005 seconds)

Published: Thu Jul 30 2015