data_structure_and_algorithm -- 如何找到字符串中最长回文子串： python & java实现

def is_plalindrome(s):
    s_len = len(s)
    for i in range(s_len/2):
        if s[i] != s[s_len-i-1]:
            return False
    return True

def pre_handle_string(s):
    sb = '#'
    s_len = len(s)
    for i in range(s_len):
        sb = sb + s[i] + '#'
    return str(sb)

# 寻找最长回文字串
def find_longest_plalindrome_string(s):
    # 预处理字符串， 加 '#'
    ss = pre_handle_string(s)
    # 处理后的字符长度
    ss_len = len(ss)
    # 右边界
    right_side = 0
    # 右边界对应的回文串中心
    right_side_center = 0
    # 保存以每个字符为中心的回文长度一半(向下取正)
    half_len_arr = [0 for i in range(ss_len)]
    # 记录回文中心
    center = 0
    # 记录最长回文长度
    longest_half = 0

    for i in range (ss_len):
        # 是否需要中心扩展
        need_calc = True
        # 如果在右边界的覆盖之内
        if right_side > i:
            # 计算相对right_side_center的对称位置
            left_center = 2*right_side_center - i
            # 根据回文性质得出结论
            half_len_arr[i] = half_len_arr[left_center]
            # 如果超过了右边界，进行调整
            if i+half_len_arr[i] > right_side:
                half_len_arr[i] = right_side-i
            # 如果根据已知条件计算得出的最长回文小于右边界，则不需要扩展了
            if i+half_len_arr[left_center] < right_side:
                need_calc = False
        # 中心扩展
        if need_calc:
            while (i-1-half_len_arr[i]>=0) and (i+1+half_len_arr[i] < ss_len):
                if ss[i+1+half_len_arr[i]] == ss[i-1-half_len_arr[i]]:
                    half_len_arr[i] = half_len_arr[i]+1
                else:
                    break
            
            # 更新右边界及中心
            right_side = i + half_len_arr[i]
            right_side_center = i
            # 记录最长回文串
            if half_len_arr[i] > longest_half:
                center = i
                longest_half = half_len_arr[i]
    sb = ''
    # +2是因为去掉之间添加的#
    for i in range (center-longest_half+1,center+longest_half,2):
        sb = sb + ss[i]

    return str(sb)


if __name__ == '__main__':
    test_str = ["abcdcef",
            "adaelele",
            "cabadabae",
            "aaaabcdefgfedcbaa",
            "aaba",
            "aaaaaaaaa"]
    for per_str in test_str:
        print ("原字串 : %s", per_str)
        print ("最长回文串 : %s", find_longest_plalindrome_string(per_str))
    pass

public class PlalindromeString {

    // 判断一个字符串是否回文，算法中用不到了
    @Deprecated
    private boolean isPlalindrome(String s) {
        int len = s.length();
        for(int i = 0; i < len / 2; i++) {
            if(s.charAt(i) != s.charAt(len - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    // 预处理字符串，在两个字符之间加上#
    private String preHandleString(String s) {
        StringBuffer sb = new StringBuffer();
        int len = s.length();
        sb.append('#');
        for(int i = 0; i < len; i++) {
            sb.append(s.charAt(i));
            sb.append('#');
        }
        return sb.toString();
    }

    // 寻找最长回文字串
    public String findLongestPlalindromeString(String s) {
        // 先预处理字符串
        String str = preHandleString(s);
        // 处理后的字串长度
        int len = str.length();
        // 右边界
        int rightSide = 0;
        // 右边界对应的回文串中心
        int rightSideCenter = 0;
        // 保存以每个字符为中心的回文长度一半（向下取整）
        int[] halfLenArr = new int[len];
        // 记录回文中心
        int center = 0;
        // 记录最长回文长度
        int longestHalf = 0;
        for(int i = 0; i < len; i++) {
            // 是否需要中心扩展
            boolean needCalc = true;
            // 如果在右边界的覆盖之内
            if(rightSide > i) {
                // 计算相对rightSideCenter的对称位置
                int leftCenter = 2 * rightSideCenter - i;
                // 根据回文性质得到的结论
                halfLenArr[i] = halfLenArr[leftCenter];
                // 如果超过了右边界，进行调整
                if(i + halfLenArr[i] > rightSide) {
                    halfLenArr[i] = rightSide - i;
                }
                // 如果根据已知条件计算得出的最长回文小于右边界，则不需要扩展了
                if(i + halfLenArr[leftCenter] < rightSide) {
                    // 直接推出结论
                    needCalc = false;
                }
            }
            // 中心扩展
            if(needCalc) {
                while(i - 1 - halfLenArr[i] >= 0 && i + 1 + halfLenArr[i] < len) {
                    if(str.charAt(i + 1 + halfLenArr[i]) == str.charAt(i - 1 - halfLenArr[i])) {
                        halfLenArr[i]++;
                    } else {
                        break;
                    }
                }
                // 更新右边界及中心
                rightSide = i + halfLenArr[i];
                rightSideCenter = i;
                // 记录最长回文串
                if(halfLenArr[i] > longestHalf) {
                    center = i;
                    longestHalf = halfLenArr[i];
                }
            }
        }
        // 去掉之前添加的#
        StringBuffer sb = new StringBuffer();
        for(int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) {
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }

}

public class Main {

    public static void main(String[] args) {

        PlalindromeString ps = new PlalindromeString();

        String[] testStrArr = new String[] {
            "abcdcef",
            "adaelele",
            "cabadabae",
            "aaaabcdefgfedcbaa",
            "aaba",
            "aaaaaaaaa"
        };

        for(String str : testStrArr) {
            System.out.println(String.format("原字串 : %s", str));
            System.out.println(String.format("最长回文串 : %s", ps.findLongestPlalindromeString(str)));
            System.out.println();
        }

    }

}