The title

Given a string s, find the longest subroutine in s. You can assume that the maximum length of s is 1000.

Example 1: Enter:"babad"Output:"bab"Note:"aba"It's also a valid answer. Example 2: Enter:"cbbd"Output:"bb"
Copy the code

Train of thought

  1. Method of violence. 2 layers of loop nesting, traversing all substrings. Determine whether the substring is palindrome and compare the largest start and end subscripts saved. Check whether the substring is palindrome by intercepting strings before and after the comparison. If they are equal, they are drawn to both sides, and the indices of direct contrast are equal and the values are in the same place. If not equal, the substring is non-palindrome.
  2. Center spread algorithm. Palindrome strings have a characteristic of left-right symmetry. If it is an odd-length palindrome string, the middle character acts as a point of symmetry, as in ABA. If it is a palindrome string of even length, the middle two characters are used as symmetry points, such as bb in ABba. So when you compare, just find the center point and expand the comparison on both sides. Until symmetry is broken, compare the start and end coordinates of the longest loop substring with the current length. If the current substring length is large, update the start and end coordinates. Due to the existence of odd and even lengths, the corresponding center point is different, but the two modes may produce a reply substring, all the matching of the two modes should be matched, and take the same center point of the two modes of longer update start and end coordinates, this is the details that need to deal with when coding.

Coding details

1. In order to obtain the last substring, we need to temporarily save the startIndex and endIndex coordinates. 2. The default odd number matching mode, by judging whether the current element is equal to the element after it to determine whether to meet the even number matching.

char* longestPalindrome(char* s) {

    int startIndex = 0 ;
    int endIndex = 0;

    int len = strlen(s);
    for (int i = 0; i < len; i ++) {
        int frontIndex = i ;
        int nextIndex = i;

        bool evenSerech = true; // Meet even matching modeif (s[i] == s[nextIndex + 1]) {
            evenSerech = true;
        }
        while (frontIndex > -1 && nextIndex < len && s[frontIndex] == s[nextIndex]) {
            frontIndex --;
            nextIndex ++;
        }
        int current = --nextIndex  + 1 - ++frontIndex ;
        if (current > (endIndex + 1 - startIndex)) {
            startIndex = frontIndex;
            endIndex = nextIndex;
        }

        if (evenSerech) {
            frontIndex = i ;
            nextIndex = i + 1;
            while (frontIndex > -1 && nextIndex < len && s[frontIndex] == s[nextIndex]) {
                frontIndex --;
                nextIndex ++;
            }
            int current = --nextIndex  + 1 -  ++frontIndex ;
            if (current > (endIndex + 1 - startIndex)) {
                startIndex = frontIndex;
                endIndex = nextIndex;
            }
        }
    }
    char *p = (char*)malloc(sizeof(char*) * (endIndex + 1 - startIndex));
    int j = 0;
    for (int i = startIndex; i <= endIndex; i ++) {
        p[j ++] = s[i];
    }
    return p;
}
Copy the code

Summary: Take careful analysis of the characteristics of the palindrome, palindrome string length points even and odd length two cases (the topic carefully and analyze the topic request, some necessary points can’t be ignored, it is very important, card time more is to want to by modifying the start-stop pointer position to fit the even mode, found how can adapter odd-even two cases at the same time, If the two types of cases cannot be easily handled together, switch back to separate cases). In addition, this problem can reverse the string to take the same substring method (pit), dynamic programming and Manacher algorithm to deal with, later learn to learn.

Our r (‘ω’) pioneered (‘ω’) “….