leetcode-no5

/*
 * Copyright,ShanNong Inc,2018 and onwards
 *
 * Author:fanghua fan
 */

package com.fanghua.algorithm.divideandconquer;

/**
 * Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
 * <p>
 * Example:
 * Input: "babad"
 * Output: "bab"
 * <p>
 * Note: "aba" is also a valid answer.
 * <p>
 * Example:
 * Input: "cbbd"
 * Output: "bb"
 */
public class SolutionNum5 {
    /**
     * 第一式：动态规划解法
     * 两层深度遍历，左右两边同时遍历，
     * 使用二维数组存储各个回文串开始和结束位置，
     * 找到左右两边字母相同且以及子串回文，
     * 时间复杂度是O(n^2)
     *
     * @param s
     * @return
     */
    public String longestPalindromeDynamic(String s) {
        int n = s.length();
        String res = null;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j)
                        && (j - i < 3 || dp[i + 1][j - 1]);
                if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }

    /**
     * 第二式：中心开花式
     * 全遍历一次字符串，以每个字符为中心进行回文判断，直到回文结束为止
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

    /**
     * 第三式：Manacher算法
     * Manacher法只能解决例如aba这样长度为奇数的回文串，
     * 对于abba这样的不能解决，于是就在里面添加特殊字符。
     * 我是添加了“#”，使abba变为a#b#b#a。
     * 这个算法就是利用已有回文串的对称性来计算的，具体算法复杂度为O(N)
     * @param s
     * @return
     */
    public String longestPalindromeWithManacher(String s) {
        char[] chArray = s.toCharArray();
        int len = chArray.length * 2 + 3;
        char[] nch = new char[len];
        nch[0] = '@'; // 3. 添加特殊字符，防止访问越界
        nch[len-1] = '$';
        for (int i=1; i<len-1; i++) {
            if ((i & 1) != 0) {
                nch[i] = '#'; // 1. 在字符串中添加特殊字符，将两种情况统一解决
            } else {
                nch[i] = chArray[(i>>1) - 1];
            }
        }
        int[] p = new int[len];

        int maxid = 0, center = 0, longest = 1, longestCenter = 0;
        for (int i=1; i<len-1; i++) {
            // 2. 算法的精华
            if (maxid > i) {
                p[i] = Math.min(p[2*center-i], maxid-i);
            } else {
                p[i] = 1;
            }
            while (nch[i-p[i]]==nch[i+p[i]]) {
                p[i]++;
            }
            if (p[i]+i > maxid) {
                maxid = p[i]+i;
                center = i;
            }
            if (longest < p[i]) {
                longest = p[i];
                longestCenter = center;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i=longestCenter+1-longest; i<longestCenter+longest; i++) {
            if (nch[i] != '#')
                sb.append(nch[i]);
        }
        return sb.toString();
    }

}