Manacher's Algorithm | Code Tutorial and Explanation

okay so hey guys it's Quinton and today we are going to talk about the manicures algorithm so in the previous videos we found how to calculate the longest palindrome substring but the methods that we used well they were incredibly difficult for the computer to process they had incredibly high complexities and well they were difficult this is because the complexity of the algorithms was incredibly high so we had to find other methods which we are going to cover in this video this algorithm finds the longest palindrome substring in Big O of n complexity which is incredibly useful for us so if we have a string like a B a a b c that's what we are going to experiment on the first step is called separation in the separation method you basically place symbols in between the characters to make sure that even if the strings are of even or odd character lengths you know odd characters even whatever it wouldn't matter okay it wouldn't matter we are going to use the separation symbols of hash so pound hash whatever so let's go ahead and do it and then we get the string hash a hash B hash a hash a hash B hash C try saying that with the mouthful so let's talk about another property let's talk about mirroring as you can see we have two rows here one row is a modified string and the other row is a row of numbers which is actually an array that we will denote by P if you observe closely the numbers in P correspond in some way with the string I don't know what way but that's some way check the first character beam text the posted instantiation of be the corresponding value in P for B is 3 C if you expand the string towards the left and the right from be expanding your means trying to find the palindrome which centers at B so here that Center will be basically collecting three characters in the left and three characters on the right and that gives you a palindrome of hash a hash B hashe has B with B at the center of course if you look closer a little bit closer a little bit more closer the numbers on the left of 3 and the right of 3 are to an extent mirror images of each other does that not blow your mind this is the holy grail on top of which the entire algorithm is built but but is this a coincidence or a tried-and-tested property well it's a bit of both the entire of our AP or AP okay it's created in such a fashion by storing the values which we find by expanding and mirroring in the corresponding location in P let's take an example for better understanding of course I mean nobody understands without examples these days we have our string here okay which is altered by the symbols hash hash we have an iterator which is going to go over all of the characters in the screen one after the other and we also have an array at the bottom which is going to store all the numbers that we come across in the program which is basically the denoted by P as we talked about earlier and also we have the mirroring line the mirroring line as you see the dashed line is the line along which the current mirroring process is going to exist we're going to check the mirroring process by using that mirroring line pretty interesting of course all the values are set to zero initially and so let's begin our quest to find the longest palindrome substring the first letter doesn't really have a lot of prospects here its value is bound to to be zero because there are no characters on the left hand side moving on to the next character we encounter a now expanding on the left and right gives us a value of 1 1 because there is one character on either side of a which when combined with a gives us a palindrome which is hash a hash hence we store 1 in our array now that we have found a palindrome we will update our mirror line and make it point to a ok we also set left and right markers to indicate where the palindrome begins and where it ends corresponding to the current mirror Center we move to the next character once we move we realize that the current character and R are the same ok the mirroring property does not work well for the start and end characters of the palindrome it just doesn't usually because by being at the edges at the ends and starting there mirror counter parts are always mostly values of 0 which anyway is the default starting values there is no use in wasting processing power over them we directly move to expanding them on the right and left ignoring their mirror in this case you can't even expand it as it has an A on the left and on the right effectively ending its career of being a palindrome I'm sorry man you are not a palindrome next we move on to our first B the B is outside our scope of mirroring and as you can't really do much with the property of mirroring so we proceed to expand it and get the palindrome hash a hash V cash a hash now that our pointer is outside I we can effectively update our bounds of the markers Ln R and the mirror line itself and that is what we do the next character is the first one which fits the bill for applying the mirror property on when you think about it the value here has the maximum potential to be an index of our minus index of pointer which is to write the index at R minus the index of pointer get that counter to get a value of 2 this is because we are mirroring from 3 right the character has a value of 3 at the Marine Center so the maximum value that it can hold on on the right hand side is 2 which is 3 minus 1 which is interesting right it makes sense yeah but the value which we will choose is the minimum between the mirror value which is on the left hand side and the index of our minus the index of pointer which is 0 versus 2 so which is smaller as a result we choose 0 because 0 is smaller we put 0 in our value array that is P and try to expand it but it doesn't form any palindrome and hence that validates our hypothesis we can't update any of the parameters here as our pointer is still bound by R and L the next step is moving to the next character we use the same method as above to calculate against either using the mirror image of that value or index of R or index of pointer and you subtract those right you subtract the index of R minus the next pointer we realize that both are the same and so we place one of them at the index it becomes 1 right we still can't update any of our parameters here as you know the mirror line and stuff as our pointer is still bound by the R and L now we sit on the location of our we said earlier that the mirroring property does not work well for the start and end characters of the palindrome the same applies here so we just set it to 0 and start expanding after expanding we get the value of 4 which is crazy this means that the string we encounter was hash be hash a hash a hash be hash which has a length of I in four plus four plus one we said the value and now must decide whether to update the mirror line or not so when we do officially update the mirror line I don't know do we update it when the pointer the index is a pointer plus the value as of P as the index of the pointer is greater than the index of R which means that we'd I plus the value stored at P of I to be greater than R and that gives us the value if it is you know extending beyond past R and then only then have V to set new bounds for checking the new characters if we if the palindromes that we found that never expanded beyond our there was no need to update the mirror lines because I will always be less than R them it it makes sense right if your pointer doesn't extend beyond our wiser why in god's name are you trying to do that it makes no sense right moving to the next character we find an obvious use case for using the mirror values expanding doesn't give us anything and we move the next character we apply the same principle zero and we get the same result next we face a new challenge the value of R minus the value of the index of R minus the index of pointer is less in this case as opposed to the previous previous case and the mirror value and we swore to always use the minimum of them both hence we use index of our minus index of pointer that value and that is the correct one as expanding doesn't give us anything hence that is how you finish up with the last C expanding to one and the last character is expected to be zero because zero you know there's no character to the right of it and and that is how this algorithm works you know and then basically go through the entire of P and find out what value is the maximum and you basically get the value of what you want at the end and that's the palindrome this algorithm is truly not straightforward let's take a look at the code so this is the code for the manicures algorithm it starts with you pre-processing the string because you want to add all of those hashes so in the pre process function you basically take a character array which is a string you find the length of that string you basically create a string which is two x plus one the length of that particular string because hey you want to store those hashes along with the characters so if you calculate the hashes plus the characters are going to be a grater by a margin they want to be graded by a margin plus I also want to have us appear a definitive space for to store all those characters next I also have a temp pointer because I don't want to use my original pointer to basically go through the entire list I want to use a 10 pointer because the 10 point will basically act as a temporary pointer without me ruining the pointer of my array and this is in C++ obviously so I'm using pointers over here I'm basically setting the first you know the first hash over here and 10 plus plus and basically I'm going through one by one one by one all of the hashes taking a character at a time taking a hash at a time character hash character hash and that's what I'm returning I'm returning the pointer to the string which I just created and that's pretty simple so once we're done with the pre-process function we take the length of that particular string take the length and basically put it in this variable called length then we define the star P Row the row which will store our palindrome numbers you know all the numbers we talked about below are in the second row yeah those numbers are going to be stored over here in the star P array the next part is we define to two variables one is the variables C and one is the variable R now these two variables are very important we don't define L if you observe we don't define out because we don't need it we don't need to find L because whatever L provides is we can actually calculate it by using something like this I'm Merve of you know expression so C is basically the mirror line if you see the presentation the mirror line is basically where C will be pointing to that will act as the index of the mirror line and R will be the index of where we are going to end our bounds on the right hand side okay now let's start iterating through the entire string one by one so this is the for loop the iterator loop which is going to help us iterate through the entire entire string we have the eye mirror now what is a mirror I'm mirror is basically going to be the value that is going to be the mirror index of the value that I'm currently pointing to so if I'm pointing to say the mirror index is C and I'm and I'm basically as a character which is to the right of C and basically I want to find the mirror index the index of the mirror character this is what I'm going to use see these bases the mirror index minus I minus C so I minus C will give me that value which is the mirror index that value I'll subtract with C which will reduce the the index by that amount and that will basically give me the mirror index of III underscore mirror index next I'm going to check if R is greater than I and we have done this numerous amounts of times in the presentation if R is greater than I if the right bound is greater and the eye is less than the character which I'm iterating on has a lower index than the odds are is out of bounds if that's the case then I'm basically going to pick the minimum pick the minimum of R minus I or because R - I can obviously be the maximum value which can be attained by that particular character in the array P or I'm going to choose the P of mirror so whichever is minimum I'm going to choose that and then I'm going to expand so this while loop is basically for expansion what it does is it basically takes your eye adds one to it and then takes your the value which P of I stores basically because because P of I is already having that amount of character so if you have P of I equal to two the array P already knows that you have two characters on your left and right which form a palindrome that's what I'm doing over two characters plus one because I want to extend my bounds I want to expand my bounds by one and then I basically do I have P of I plus plus if I found that both of them on the plus 1 and the minus 1 are the same so that basically gives you a palindrome and that's why I use P of I plus plus pretty simple stuff next I'm going to update the my C location and our location now what what are the what are the you know conditions for this update basically the conditions are very simple is that if you if you extend your bounds if I plus P of I is greater than R ok if you extend your balance if you're if the current if the current index at which you are extends the bounds beyond are beyond are then you basically have to update your variables and that is exactly what we're doing here we saw all of this in the presentation it's all here C will be I and R will be I plus P of I because you know how much how far our is supposed to be from the center of the mirror Center and basically I'm just printing out see I probably don't need this here right now all the code will be in the description guys so don't worry about this next what I'm going to do is I'm basically I'm basically going over the entire length of P and picking out the most the largest value of P and once I get that value I'm going to post process basically post process basically means that I'm going to remove the hashes of the substring which I get substring is the string which I get from the center - max length and center plus max length so max then - Max and Plus you basically get the palindrome of that substring and that's about it I post the post process function is also pretty simple it basically just whenever it finds like a hash it doesn't include it and everything else it includes into the spring and return returns it's pretty simple guys the code in the description thanks for watching I hope you found this video helpful because the manikins algorithm is however much people denied it is kind of convoluted a little complicated but yeah I hope this helps and thanks for watching guys I will see you in the next video please like share and subscribe because these kind of videos are very hard to make you know you have to think about a lot of things and yeah I really appreciate a subscribe i and i really appreciate alike and I really appreciate you sending me messages commenting and and all that good stuff so later guy

Channel: Quinston Pimenta

Views: 34,468

Keywords: Computer, Science, Student, Code, Algorithm, Programming, College, Coding, Java, Tutorial, Data, Structures, Sorts, Graphs, C++, Killing, it, with, Learning, How, to, code, in, Manachers algorithm, longest palindrome substring explanation, code tutorial, manachers, palindrome, substring, how to find

Id: kbUiR5YWUpQ

Length: 14min 35sec (875 seconds)

Published: Fri Jan 20 2017