If you want to talk about the horse-drawn cart algorithm, you have to talk about this problem, find the longest loop substring, horse-drawn cart algorithm is one of the solutions, I don’t have much to say, straight down:

Topic describes

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

example

Example 1: Input: s = "babad" Output: "bab" Explanation: "ABA" is also the answer to the question. Example 2: Input: s = "CBBD" Output: "bb" Example 3: Input: S = "A" Output: "A" Example 4: Input: s = "ac" Output: "A"Copy the code

Horse-drawn cart algorithm

This is a wonderful Algorithm, which was invented by a man named Manacher in 1957, so it is called Manacher’s Algorithm. It is mainly used to find the longest substring of a string. The biggest contribution of this Algorithm is to improve the time complexity to linear. The time complexity of dynamic programming is O(n2).

If there are n characters, there are n+n+1 centers: if there are n characters, there are n+n+1 centers:

To solve the problem where the center might be a gap, we insert a “#” into each character gap. To make the end of the extension clear, we insert a “^” into the left boundary and a “$” into the right boundary:

S stands for the string after inserting “#”,”^”,”$”, etc. We use an array P to represent the length of each character in S that can be extended to both sides:

For example, P[8] = 3, which means that we can extend the palindrome string by 3 characters, so that the length of the palindrome string is 3, and the string after removing # is ACA:

P[11]= 4, which means that 4 characters can be extended to both sides, that is, the length of the palindrome string is 4, and the string after removing # is CAAC:

Assuming we already know the array P, how do we get the palindrome string?

Subtracting P[I] (the length of the palindrome string) from index of P yields the index of the beginning of the palindrome string in the extended string S, and dividing by 2 yields the index in the original string.

So now the question is: how do I solve the array P[I]?

In fact, the key to the horse-drawn cart algorithm is that it makes full use of the symmetry of palindromes and uses the existing results to help calculate the subsequent results.

Suppose the maximal palindrome string at the character index position P has been calculated with the left boundary being PL and the right boundary being PR:

So when we find a position I, I is less than or equal to PR, we can actually find the point j of symmetry of I with respect to P:

Then assuming that the length of the longest palindrome centered on j is len, and in the range PL to P, so is the length of the longest palindrome centered on I:

The length of the longest subroutine centered on I is equal to the length of the longest subroutine centered on j

But there are two problems:

  • The previous palindrome string, P, which was it?
  • What are the special circumstances? How to deal with special cases?

(1) The previous palindrome string P refers to the right most palindrome string with the right boundary calculated previously, because in this way it is most likely to cover the index centered on I that we want to calculate now, so the symmetry of the previous results can be reused as much as possible.

Because of this, we need to keep updating the center and right boundary of P for each calculation.

(2) The special case is that the calculation of the longest palindrome string of current I cannot use the symmetry of P point, for example:

  1. In order toiThe right boundary of the palindrome string is outPThe right boundary of PR:

The solution to this situation is: the excess part needs to be expanded according to the central expansion method.

  1. iNot toPAs the center of palindrome string, can only be handled in accordance with the center expansion method.

The specific code is as follows:

    // Construct a string
    public String preProcess(String s) {
        int n = s.length();
        if (n == 0) {
            return ^ "$";
        }
        String ret = "^";
        for (int i = 0; i < n; i++)
            ret = ret + "#" + s.charAt(i);
        ret = ret + "# $";
        return ret;
    }

    // The cart algorithm
    public String longestPalindrome(String str) {
        String S = preProcess(str);
        int n = S.length();
        // Save the length of the palindrome string
        int[] P = new int[n];
        // Save the right-most palindrome center and the right border
        int center = 0, right = 0;
        // Start with the first character
        for (int i = 1; i < n - 1; i++) {
            // Find the symmetry of I about the front center
            int mirror = 2 * center - i;
            if (right > i) {
                // I is in the range of the right boundary, look at the length of the palindrome string at the symmetry point of I, and the length from I to the right boundary, take the two smaller ones
                // Do not overflow the previous boundary, otherwise center expansion is required
                P[i] = Math.min(right - i, P[mirror]);
            } else {
                // Out of range, center expanded
                P[i] = 0;
            }

            // Center expansion
            while (S.charAt(i + 1 + P[i]) == S.charAt(i - 1 - P[i])) {
                P[i]++;
            }

            // See if the new index is further to the right than the previous right-most palindrome string
            if (i + P[i] > right) {
                // Update center
                center = i;
                // Update the right borderright = i + P[i]; }}// Find the longest palindrome string through the palindrome length array
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < n - 1; i++) {
            if(P[i] > maxLen) { maxLen = P[i]; centerIndex = i; }}int start = (centerIndex - maxLen) / 2;
        return str.substring(start, start + maxLen);
    }
Copy the code

As for the complexity of the algorithm, space complexity with the aid of the array of size n, to O (n), and time complexity, appears to be in the two layers of circulation, but it is not O (n2), but O (n), because most of the index position will directly use of the previous results and symmetry, often several times to get the results, and those who need to expand, the Because it is beyond the scope covered by the previous results, it needs to be expanded. The results obtained by expansion are conducive to the calculation of the next index position, so the expansion is actually less.

[Author profile] : Qin Huai, public number [Qin Huai Grocery store] author, the road of technology is not at that time, mountain high water long, even slow, chi and not stop. Personal Writing Direction: Java source code analysis, JDBC, Mybatis, Spring, Redis, distributed, sword Offer, LeetCode, etc., carefully write each article, do not like the title party, do not like the flowery, mostly write a series of articles, can not guarantee that I write are completely correct, But I guarantee that what I write is done through practice or research. We hope to correct any omissions or mistakes.

Offer all questions in PDF

What did I write about 2020?

Open Source Programming Notes