Given a string, find the longest length of palindrome starting from the left.
For example:
abaeab, the longest from left is aba, so return 3.
abcbaef, the longest from left is abcba, so return 5.
ababa, the longest from left is ababa, so return 5.
One of the solution is to use rolling hash, which I wrote in previous post link.
Here is a better solution, which the idea is from calculating next array in KMP.
Take abae for example, let’s add the reverse to the right: abaeeaba.
Let’s implement KMP next function. To begin with, we set i=0, j=4. Then, let’s find the max next_value.
We can find the max next_value in O(n) time. In this example, the max next_value is 3. And that is the result.
Take another example, abbaaba, the process is like below:
check my code on github: link