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 😟😟