Nuggets team number online, help you Offer impromptu! Click to view spring recruitment positions in big factories

I. Title Description:

Given a string s, find the longest substring in s.

Example 1:

Input: s = "babad" Output: "bab" Explanation: "ABA" is also the answer to the question.Copy the code

Example 2:

Input: s = "CBBD" Output: "bb"Copy the code

Example 2:

Input: s = "a" Output: "a"Copy the code

Example 2:

Input: s = "AC"Copy the code

Subject address: leetcode-cn.com/problems/lo…

Ii. Analysis of Ideas:

Manachar algorithm can only solve the problem of an odd number of strings of the context substring. When the string is odd, Manachar algorithm will solve the length of the palindrome radius with each character as the axis of symmetry. The solution process is similar to the center extension algorithm, which takes the axis of symmetry as the center and extends to both sides until the characters on both sides are inconsistent or the boundary is encountered.

The genius of Manachar’s algorithm is to exploit the symmetry of palindrome strings.

1. Solve the problem that the odd and even lengths of strings are inconsistent.

Inserts a special character between each character. For example: abba -> #a#b#b#a#. So this will make sure that all the inputs are odd.

2. palindrome radius

Define an array RL so that RL[I] represents the palindrome radius of the string at position I (we call the distance between the left-most or right-most character in a palindrome string and its axis of symmetry); Find the longest substring by evaluating the RL array. The problem turns to solving the RL array. Palindrome radius comparison:

char:    # a # b # b # a #
 RL :    0 1 0 1 4 1 0 1 0
Copy the code

3. Use the symmetry of palindrome string to solve RL

Hypothesis: RL[0.. pos] has been solved, and RL[pos] = rad, we want to solve RL[pos + k] (k < pos * 2) value (p.s: according to the hypothesis, it can be known that the string [0.. pos * 2] is pos symmetric palindrome string)

[0.. pos * 2] is a palindrome string, but the value of RL[pos + k] is not known

|-----------#-------*--------#----------|
          pos-k    pos      pos+k      pos*2  
Copy the code

Because of the symmetry of palindromes, RL[pos + k] and RL[pos -k] have three cases:

3.1 RL[pos -k] < RL[pos] – (pos -k)

The palindrome length at pos -k does not exceed the palindrome length at pos. RL[pos + k] = RL[pos -k] according to the symmetry of the palindrome string.

        ****|****        ****|****
|-----------#-------*--------#----------|
          pos-k    pos      pos+k      pos*2 
Copy the code

RL[pos -k] > RL[pos] – (pos -k)

The palindrome length at pos -k exceeds the palindrome length at POS.

RL[pos] = RL[pos] – (pos -k) RL[pos] = RL[pos] – (pos -k)

                      **********|**********
***********|**********          |
 |---------#---------*----------#----------|
         pos-k      pos       pos+k      pos*2 
Copy the code

From the above analysis, it can be known that if RL[pos -k]! = RL[pos] – (pos – k)

RL[pos + k] = min(RL[pos - k],RL[pos] - (pos - k))
Copy the code

3.3 RL[pos -k] == RL[pos] – (pos -k)

As shown in the figure below, according to the symmetry of palindromes, RL[pos + k] >= RL[pos -k], that is, the minimum value of RL[pos + k] is RL[pos -k].

                    
********|********       ********|********
|-------#-----------*-----------#--------|
          pos-k    pos      pos+k      pos*2 
Copy the code

We move pos to pos + k out and return to 3.1 loop judgment.

4. Use RL to solve the longest loop substring

By traversing RL, the position center where the symmetry axis of the largest palindrome string is located and the maximum palindrome radius Max are solved.

s.substring(center - max ,center + max + 1).replace("#",""); // Don't forget to remove the added special characters.Copy the code

Iii. AC Code:

public String longestPalindrome(String s) { StringBuilder sb = new StringBuilder(); sb.append("#"); for (int i = 0; i < s.length(); i++) { sb.append(s.charAt(i)); sb.append("#"); } int[] RL = new int[sb.length()]; for (int pos = 1, rad = 0, k; pos < sb.length() - 1; Pos += k) { Rad [pos] while (pos-rad > 0 &&pos + rad < sb.length() -1 &&sb.charat (pos-rad-1) == sb.charat (pos + rad + 1))  { rad++; } RL[pos] = rad; RL[pos +k] for (k = 1; k < RL[pos] && RL[pos - k] ! = RL[pos] - k; k++) { RL[pos + k] = java.lang.Math.min(RL[pos - k], RL[pos] - k); Pos = pos +k rad = java.lang.math.max (pos [pos -k], 0); } int max = 0; int center = 0; for (int i = 0; i < RL.length; i++) { if (RL[i] > max) { max = RL[i]; center = i; } } s = sb.substring(center - max, center + max + 1).replace("#", ""); return s; }Copy the code

Four,

Note the test data:

"aaab"
"ababac"
"abbb"
Copy the code