给定字符串的最长回文子串

题目：求解给定字符串的最长回文子串

分析：什么是回文？通俗来讲就是一段字符串，正着读和反着读都是一样的。例如aba，abccba。会发现回文是很完美的对称字符串。

解决方案一：暴力破解

具体实现：求出给定字符串的所有的子串，针对每个子串与其倒置的串进行比较，若相等就是回文。

private static void getHuiwenString(String input){
        for(int i=0; i<input.length();i++){
            StringBuilder stringBuilder =new StringBuilder();
            stringBuilder.append(input.charAt(i));
            if(stringBuilder.toString().equals(stringBuilder.reverse().toString())){
                System.out.println(stringBuilder.toString());
            }
            for(int j=i+1; j<input.length(); j++){
                stringBuilder.append(input.charAt(j));
                if(stringBuilder.toString().equals(stringBuilder.reverse().toString())){
                    System.out.println(stringBuilder.toString());
                }
            }
        }
    }

解决方案二：Manacher算法

具体实现：将原有的字符串进行改造，字符串中的两两字符之间插入一个桩（这个可以用一个特殊字符代替），这样的好处是无论原有的字符串的长度是奇数还是偶数，经过改造后都变成了奇数。例如我在文章开头举的例子：aba，abccba，就变成了#a#b#a#，#a#b#c#c#b#a#。这样字符串都有了一个中心。求解回文就是选中某个点然后向两边扩展，如果左右两边的字符相等就继续扩展，否则就退出。

public class HuiWen {
    public static void main(String[] args) {
        String input = "abbabbaabb";
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            stringBuilder.append("#");
            stringBuilder.append(input.charAt(i));
        }

        stringBuilder.append("#");

        System.out.println(stringBuilder);

        input = stringBuilder.toString();

        for (int i = 0; i < input.length(); i++) {
            String myString = getLongestString(input, i).replaceAll("#","");
            if(StringUtils.isNotEmpty(myString)){
                System.out.println(myString);
            }
        }

    }

    private static String getLongestString(String input, int mid) {
        int len = input.length();
        StringBuilder stringBuilderLeft = new StringBuilder();
        StringBuilder stringBuilderRight = new StringBuilder();
        stringBuilderRight.append(input.charAt(mid));
        for (int i = mid, j = mid; i > 0 && j<len-1; i--, j++) {
            if (input.charAt(i - 1) != input.charAt(j + 1)) {
                return stringBuilderLeft.reverse().append(stringBuilderRight).toString();
            }

            stringBuilderLeft.append(input.charAt(i - 1));
            stringBuilderRight.append(input.charAt(j + 1));
        }

        return stringBuilderLeft.reverse().append(stringBuilderRight).toString();
    }
}

总结

暴力破解法两次for循环，时间复杂度就是O(n2)，验证是否是回文，最多就是O(n3)。Manacher算法只需要一遍循环，再加上一遍扩展，时间复杂度最多是O(n2)。当字符串长度比较短时，确实看不出来谁优谁劣，但字符串很长时，就会发现暴力破解法会找出很多非最长回文的字符串，此外，Manacher算法还有优化的空间，例如如果找到已有的最长的回认为文长度超过后续锚点位置两边能扩展的最大长度，即可认为这就是最长回文。