This is the 13th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021
Manacher algorithm is used to solve the problem of finding the longest loop substring in a string. Before we get into Manacher’s algorithm, let’s look at a few concepts:
- Palindrome diameter: The length of a palindrome string centered on one character.
For example, “abcba”, the palindrome diameter of the first A is 1, and since it can’t expand to either side, the longest substring centered around it is itself. The palindrome diameter of C is 5, because the longest palindrome string centered around it is “abCBA”.
- Palindrome radius: The length from the left/right margin of a palindrome string to the center character, centered on one character.
- Palindrome radius array: Stores the palindrome radius for each character.
- Right-most palindrome right boundary: The right-most boundary at which a string of texts has been recorded.
We denoted the right-most palindrome right boundary as R with an initial value of -1. Again, taking “abCBA” as an example, the longest subroutine centered on the first A is itself, so the right boundary of the rightmost palindrome can be updated to 0, and it will be updated to 4 by the time it reaches C, and it won’t be updated after that because the right boundary of the longest subroutine centered on the second B and the second A is less than or equal to 4.
- Right-most palindrome right-boundary center: The center of the palindrome string corresponding to the first time the right-most palindrome right-boundary has been reached, denoted C, also initialized to -1.
With these concepts in mind, the current position in the string is denoted as I, which can be divided into the following two big cases:
(1) I is not in the right boundary of the right-most palindrome
In this case, we can’t accelerate, we have to keep expanding
(2) The large case that I is in the right boundary of the most right palindrome can be subdivided into the following cases: the symmetric point of I in the center of the right boundary of the most right palindrome is I ‘, and L is the left boundary of the most left palindrome:
- The expanded region of I ‘is between (L, R), as follows:
In that case, we can make sure that the palindrome radius of I is the same as the palindrome radius of I prime.
- The palindrome range of I ‘is not between (L,R), as follows:
In this case, the palindrome radius of I is I to R
- I ‘palindrome radius and L pressure line, as follows:
In this case, the palindrome radius of I has not been settled yet, and we have to continue to expand outward.
PS: The above examples are all odd palindromes, even palindromes are not applicable, do we have to divide the odd and even cases? Just preprocess our string and add a character (#) to each character to smooth out the parity differences. The format string method is as follows:
function formatString(str0){
let charArr=str0.split(' ');
let res=[];
let index=0;
for(let i=0; i<(charArr.length*2+1); i++){ res[i]=(i%2= =0)?The '#':charArr[index++];
}
return res;
}
Copy the code
Next, write a code for the horse-drawn cart algorithm:
function maxLcp(s){
if(s.length==0)return 0;
let charArr=formatString(s);// Preprocess the string
let pArr=[];
let C=-1;// Right-most palindrome right border center
let R=-1;// Most right palindrome right boundary
let resCenter=-1;// Save the center of the longest callback substring to return the substring
let max=Number.MIN_VALUE;// The radius of the longest loop substring
for(let i=0; i<charArr.length; i++){//R< I is the case where I is not in the right-most palindrome. R> I is the case where I is in the right-most palindrome
PArr [2* c-i], the smaller of r-i. PArr [2* c-i
pArr[i]=R>i?Math.min(pArr[2*C-i],R-i):1;
// This is to simplify the code, merge several cases, all unified expansion
while(i+pArr[i]<charArr.length&&i-pArr[i]>-1) {if(charArr[i+pArr[i]]==charArr[i-pArr[i]]){
pArr[i]++;
}
else {break;}
}
// Update the right edge of the right-most palindrome
if(i+pArr[i]>R){
R=i+pArr[i];
C=i;
}
// Update the maximum palindrome radius
if(pArr[i]>max){ max=pArr[i]; resCenter=i; }}// console.log(max);
// console.log(resCenter);
// Get the starting position of the longest substring
let start=Math.floor((resCenter-(max-1)) /2);
// console.log(start);
return s.substring(start,start+max-1);
}
Copy the code
Finally it took a little time to dig the boundary 😟😟