Can anyone tell me how are we finding starting index of original string here .This is Manchar Algorithm code In Hackerearth.I want to understand this line:-
return s.substr( (centerIndex - 1 - maxPalindrome) / 2, maxPalindrome);
Manachar Algorithm
in manachars algorithm, centre index is the index which comprises of centre of the maximum palindromic substring.
so if max palindromic substring is of length 5,and centre is index 7. But if you have gone through manachars algrithm then you must have noticed that , this INDEX 7 , is of the array which is of length 2*n+1;(where n is length of string). In short the array P[]. So if P[7] id 5 , that means at index 7(this is P[7]) we have length of maximum palindrome to be 5;
Now , according to the algorithm this P array’s 7 actually means index 3 in the original string;
Because this array P is of double lenngth (assuming you have understood the algorithm);
So basically (centerIndex - 1 - maxPalindrome) / 2 ,will give me the index of the string from which the lenth of longest palindrome of length “maxPalindrome” began. Why am I diving by 2??? Because P[i] is of length 2*n. and centreIndex if an index of P[i].
ya thanks I have understood.
@Bhawna no problem Bhawna.Pls close the doubt and give good rating if you are satisfied with response and content.
ok…
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.