1. Palindrome problem

Palindrome problem is a common algorithm problem. We often see such problems when we brush the questions. The common solution is the violent solution.

Violent solution 1.0

  • The brute force solution is to split the string into palindromes and determine whether it is a palindrome string one by one, but there is a big bug with this solution. When the string is odd, the longest palindrome string cannot be counted.

So we need to make an optimization of the solution of this violence, and make it optimization 2.0

  • By changing the string, placing a special character (any character will do) around each string, and then looking for the palindrome string one by one, you can ensure that the palindrome string you find is the largest. But the time complexity of this optimized violent solution is still worrying, O(N^2).

2. Manacher algorithm

This algorithm is to optimize the violence method of an algorithm, the algorithm contains three points

  • 1. Palindrome radius array parr[] : stores the length of each palindrome string

  • 2. The right-most palindrome boundary R marks the right boundary of the largest palindrome string that has been traversed

  • 3. Palindrome center point C, marks the right boundary of the largest palindrome string that has been traversed

Turn the string into an array of characters while traversing, the position of the subscript I for the right boundary R has 3 cases

  • 1. If the subscript I is outside the right boundary R, only the brute force method can be used to calculate the palindrome string centered on this subscript

  • 2. The palindrome length of the symmetric point I ‘with respect to C of subscript I is exactly on the left boundary, find the symmetric point I’ with respect to the center point C, and obtain the length of parr[I ‘]. If its palindrome range is within the range of the largest palindrome string with the right boundary R, The maximum palindrome string with subscript I is parr[I ‘].

  • 3. The palindrome length of the symmetric point I ‘about C of subscript I is just on the left boundary, so it is necessary to continue the violent comparison of the numbers outside the boundary R to obtain the length of the palindrome string with subscript I as the center point.

The code is as follows:

* Solution one: violent method will be given a string to all processing, in the middle of each character is added a specific character, and then each character of the spread of the search, write down the length of each palindrome string, and finally compare the length of all palindrome characters O(N^2* * * Solution two: Manacher algorithm, set three conditions,1.A palindrome radius array parr[]2.The rightmost palindrome boundary R3.The palindrome center * parr[] array is the length of all palindrome strings, or if there is only one1, * R represents the rightmost boundary of the longest palindrome string, and the palindrome radius is equal to R- center point * C represents the center point of each palindrome string * the initial values of R and C are both -1
     *O(N)
     */



    public static int manacherDetail(String s){
        if(s == null || s.length() == 0) {return 0;
        }
        char[] str= manacherString(s);
        int[] parr = new int[str.length];
        int R = -1;
        int C = -1;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i<str.length; i++){// Each element in parr[] is initialized to 1. If I is inside the right boundary R of the current largest palindrome string, the center point C of the largest palindrome string is taken to find its symmetry point in the parr array
            // If the palindrome range of the symmetry point is already outside the range of the maximum palindrome string, take the minimum value of bothparr[i] = R>i ? Math.min(parr[2*C-i],R-i):1;
            // If the parr element has a range, the palindrome radius is increased by 1. If not, the loop is broken
            while (i + parr[i] < str.length && i - parr[i] > -1) {
                if (str[i + parr[i]] == str[i - parr[i]]) {
                    parr[i]++;
                }else {
                    break; }}// If a larger palindrome string appears, move the right-most boundary and change the center point
            if (i + parr[i] > R) {
                R = i + parr[i];
                C = i;
            }
            // Assign Max to the maximum palindrome radius
            max = Math.max(max, parr[i]);
        }
        // The final number is subtracted by 1 due to the addition of special characters
        return max - 1;
    }

    public static char[] manacherString(String str){
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i ! = res.length; i++) { res[i] = (i &1) = =0 ? The '#' : charArr[index++];
        }
        return res;
    }
Copy the code