[LeetCode] 005.Longest Palindrom

Problem description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"

Code

class Solution {
    
    int maxLength = 2005;
    char[] c = new char[maxLength];
    char[] re = new char[maxLength];
    int[] res = new int[maxLength];
    
    void change(String s) {
        
        char b = '$';
        char m = '#';
        int len = s.length();
        c[0] = b;
        c[1] = m;
        
        for(int i = 0; i < len; i++) {
            c[i * 2 + 2] = s.charAt(i);
            c[i * 2 + 3] = m;
        }
    }
    
    String manacher(int len) {
        
        res[0] = 1;
        int id = 0;
        int mx = 1;
        
        for(int i = 1; i < len; i++) {
            if(mx > i) {
                res[i] = res[2 * id - i] < mx - i ? res[2 * id - i] : mx - i;
            } else {
                res[i] = 1;
            }
            
            for(; c[i - res[i]] == c[i + res[i]]; res[i]++);
            
            if(mx < i + res[i]) {
                mx = i + res[i];
                id = i;
            }
        }
        
        int max = res[0];
        int point = 0;
        for(int i = 1; i < len; i++) {
            if(max < res[i]) {
                max = res[i];
                point = i;
            }
        }
        
        int r, l;
        l = point - max + 1;
        r = point + max - 1;
        
        String ress = "";
        int le = 0;
        for(int i = l; i <= r; i++) {
            if(c[i] != '#') {
                ress += c[i];
            }
        }
        return ress;
    }
    
    public String longestPalindrome(String s) {
        
        int len = s.length();
        change(s);
        return manacher(2 * len + 1);        
    }
}

Analysis

• manacher算法（详细分析待补）