Written interview algorithm classic - longest palindrome substring

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Definition of palindrome

The sequence of characters that are read both forward and backward is “ Palindrome ”, Such as “abba”、“abccba” yes “ Palindrome ”,“abcde” and “ababab” It is not “ Palindrome ”. The longest palindrome substring of a string , Is the longest palindrome substring contained in a string . for example “1212134” The longest palindrome substring of is “12121”. Here are three ways to find the longest substring .

solution 1（ The central expansion method ）

Time complexity O（n^2）, The space complexity is O（1）. The idea of the central expansion method is , When traversing an element of an array , Centered around this element , Expand to both sides , If the elements on both sides are the same, continue to expand , Otherwise, stop expanding . Here's the picture ： When traversal to 3 when

But the central expansion method has a problem , Here's the picture ：

1,2,2,1 It's a palindrome string , However, the center of symmetry cannot be found , In this way, it is not easy to extend from one element to both sides , Here is a more convenient way to deal with , That's right 1,2,2,1 Fill in , For example, with # Fill as follows ：

As shown in the figure below, it will become a centrosymmetric palindrome string after filling , So when processing a string , Expand first , This makes it easier to expand the center , There is no need for special treatment of non centrosymmetric substrings . Suppose the length of the substring before filling is len Then the length of the extended or is ：2 * len+1, The length of the palindrome string before expansion can also be easily obtained from this relationship . Code

public void palindrome(String str)
    {
        if(str==null||str.length()==0)
            return ;
            // If str by null  Or the length is 0 Go straight back to .
        StringBuffer sb=new StringBuffer(str);
        for(int i=0;i<str.length();i++)
        {
            sb.append("#");
            sb.append(str.charAt(i));           
        }
        // Fill the given string .
        sb.append("#"); 

        char chs[]=sb.toString().toCharArray();
        int max_len=0;
        for(int i=0;i<chs.length;i++)
        {
            // Traverse to position i when , Yes i Expand the center 
            max_len=Math.max(subpalidromelen(chs,i), max_len);
            //subpalidromelen(chs,i), With i Expand the center for the center ,max_len  Save the length of the longest palindrome substring . 
        }
        System.out.println(max_len);
    }
// Central extension function  
public int subpalidromelen(char []chs,int i)
    {

        int len=0;

        for(int k=0;k<=i&&k<(chs.length-i);k++)
        {
            if(chs[i-k]==chs[i+k])
            {
                len++;

            }
            else {
                break;
            }
        }

        return len-1;
        // Because it is the filled string , The palindrome substring value before filling is len-1.
    }       

Copy

The above code makes two explanations ： ①palindrome() The given string is filled and traversed , Call the central extension function for each element traversed to obtain the value of the palindrome substring , And save the value of the longest palindrome substring .

②subpalidromelen() Central extension function , Returns the length of the palindrome substring .

solution 2（ Dynamic programming ）

Time complexity O（n^2）, Spatial complexity O（n^2）, If you use f[i][j] Save substring from i To j Whether it is palindrome substring , So I'm asking f[i][j] if j-i>=2 when , If f[i][j] For palindrome , that f[i+1][j-1], Must be palindromes . otherwise f[i][j] Not for palindromes . Here's the picture ：

Therefore, the recursive equation of dynamic programming can be obtained ：

Code ：

---

public void palindrome1(String str)
    {

        if(str==null||str.length()==0)
            return ;
        char chs[]=str.toCharArray();
        int max_len=0;
        boolean f[i][j]=new boolean[chs.length][chs.length];
        for(int j=0;j<str.length();j++)
        {
            int i=0;
            f[j][j]=true;
            // An element must be a palindrome string .
            for(;i<j;i++)
            {
                f[i][j]=(chs[j]==chs[i]&&(j-i<2||j>0&&f[i+1][j-1]));
                // If chs[j]==chs[i] When the length of the string is less than or equal to 2 when , It must be palindrome string , Such as  1,1, It's a palindrome string .
                // If the length is greater than 2 when , You need to judge f[i+1][j-1] Is it a palindrome .
                if(f[i][j])
                {                   
                    max_len=Math.max(max_len, j-i+1);
                }
                //max_len Save the length of the maximum palindrome substring . 
            }                       
        }
        System.out.println(max_len);
    }

Copy

Two points ：

① When the length of the substring is 1 Time must be a palindrome substring , Corresponding to the above f[j][j] = true . When the length of the substring is 2 And The two elements are the same , Is also a palindrome substring . Corresponding to the above f[i][j]= chs[i]&&（j-i<2）.

② When the length of the string is greater than 2 when , If the string is 121 when , To judge chs[j]==chs[i]&&f[i+1][j-1]), Dependent substring .

Manacher

Time complexity O（n）, Spatial complexity O（n） Observe the center expansion method above , It is found that a central extension is required when traversing each element , The information of the preceding palindrome substring is not used at all ,Manacher The core idea of the algorithm , Is to use the palindrome substring generated during the previous traversal , Here's the picture ：

The red part has been found in the figure above 3 The palindrome string of , Now how to find 3 Dexter 1,2,1 The palindrome substring of , Using the symmetry of palindrome substring , Here's the picture ：

①2*id-i,id , i Represents the subscript of the array ,2*id-i And i About id symmetry , If you use p[i], Express i The longest palindrome substring of position , In the case of the above figure p[i]=p[2*id-i], because p[2*id-i] stay 3 The left side of has been found , therefore p[i] Soon you'll get , However, when asked to the right 2 The longest palindrome of is shown in the figure below ：

② Find right 2 The palindrome substring of is not equal to the left 2 The palindrome string of , And it's longer than the one on the left , There are also the following cases ：

③ On the left 2 How is the palindrome on the right 2 The palindrome of is long .

Combine the above three situations ： In fact, the following formula can be used

because manacher The algorithm has the same problem as the above central expansion method , So first insert... Into the string #, Here's the picture ：

On top of that ： Introduce an auxiliary variable MaxRight, Represents all palindrome substrings currently accessed , The position of the rightmost character that can be reached . In addition, record MaxRight The position of the symmetry axis of the corresponding palindrome string , Write it down as pos, Their positional relationship is as follows .

We access the string from left to right to find RL, Assume that the currently accessed location is i, I.e. requirement RL[i], In the corresponding figure above ,i It must be in po Dexter (obviously). But we are more concerned ,i Is in MaxRight Left or right . Let's discuss it according to the situation .

1） When i stay MaxRight Left side

situation 1) The following figure can be used to depict ：

We know , Between the two red blocks in the figure （ Including red blocks ） The string of is palindrome ; And take i Is a palindrome string on the axis of symmetry , It overlaps with the palindrome string between the red blocks . We find i About pos The symmetrical position of j, This j Corresponding RL[j] We have already calculated . According to the symmetry of palindrome string , With i Is the palindrome string sum of the axis of symmetry with j Is a palindrome string on the axis of symmetry , Part of it is the same . Here are two more subdivisions .

With j The palindrome string with symmetry axis is shorter , It is as short as the following figure .

And then we know RL[i] At least not less than RL[j], And already know some of the i The palindrome string centered on , So you can make RL[i]=RL[j]. But in order to i A palindrome string that is an axis of symmetry may actually be longer , So we try to i Is the axis of symmetry , Continue to expand to the left and right , Until the left and right characters are different , Or reach the boundary .

With j The palindrome string for the axis of symmetry is very long , So long ：

In this case , Explain with i No part of the palindrome string for the axis of symmetry has been accessed , So we can only from i The left and right sides of the start trying to expand , When the left and right characters are different , Or stop when the string boundary is reached . And then update MaxRight and pos.

---

Code ：

public void manacher(String str)
    {
        if(str==null||str.length()==0)
        {
            return;
        }
        int len=str.length();
        StringBuffer sb=new StringBuffer(str);
        for(int i=0;i<len;i++)
        {
            sb.append("#");
            sb.append(str.charAt(i));           
        }
        sb.append("#"); 
        // First insert... Into the string # There is no need to distinguish between the two cases .
        int id=0,i=0,mx=0;
        int n=sb.length();
        int p[]=new int[n];
        int max_len=0;
        char chs[]=sb.toString().toCharArray();
        for(i=1;i<n;i++)
        {
            if(mx>i)
                p[i]=Math.min(p[2*id-i], mx-i);
                // If i In the middle of the largest palindrome substring , You can use the above analysis p[i] Express i The length of the longest palindrome substring of 
            else {
                p[i]=1;
                // otherwise p[i]=1,
            }
            for(;(i-p[i]>=0&&i+p[i]<n)&&(chs[i-p[i]]==chs[i+p[i]]);p[i]++)
            ;
            // Expand on the above basis .
            if(i+p[i]>mx)
            {
                mx=p[i]+i;
                id=i;
            }
            // If i+p[i]>mx, Just update mx.
            max_len=Math.max(max_len, p[i]-1);
        }   
        System.out.println(max_len);
    }   

Copy

reference ：https://segmentfault.com/a/1190000003914228

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/132955.html Link to the original text ：https://javaforall.cn