manacher算法

Manacher 回文串算法

1. 因为回文串可能有奇数个字符，也有可能有偶数个字符，奇数个字符时，处理较简单，找到轴往两边扩展就可以，而偶数个的轴有两个；所以，首先将字符串中每个字符之间插入#，那么原字符串就会变成奇数个字符。
2. 基本的求解回文串的方法：以一个字符为轴向两边扩展，两字符就继续扩
3. 基本的算法，求解i处的回文串是无法使用i之前的结论的，而manacher的快速正是因为可以基于之前的结果快速给出当前结果：
   1. 记录已求字符到达的最右边界R及此时的轴center，初始时都是-1
   2. 求第i个字符开始求回文串：
      1. 如果i在R之外或者i恰好在R上，暴力求解（从当前位开始往两边扩）
      2. 如果在R界内，求出i对于center的对称点j，j必定在已被求解过，需要讨论j处的结果是否对i有用：
         1. 若j处的回文串小于左界，即j处的回文串在当前R界和center标志的回文串中，那么i处的回文串大小等于j处，
         2. 若j处的回文串大于左界，即j处的回文串一截在当前R界和center标志的回文串中，另一截在左界的外面，那么i处的回文串大小等于i距离右界的距离（原因：在左界外面的部分不等于（不能构成回文串）在右界外的部分，而左界内的部分等于左界外的部分，所以右界内不等于右界外，右界内的部分无法扩展出界外，只能刚好到右界）
         3. 只有当i恰好在右界上，i才有可能往外扩，需要暴力求解

代码

public class Manacher {

    public static void main(String[] a) {
        Scanner scanner = new Scanner(System.in);
        String line = null;
        while(scanner.hasNextLine()) {
            line = scanner.nextLine();
            manacher(line);
        }
    }

    public static void manacher(String s) {
        int resultC = 0, center = 0, r = -1, resultR = -1;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<s.length(); i++) {
            sb.append('#');
            sb.append(s.charAt(i));
        }
        sb.append('#');
        int[] dp = new int[sb.length()];

        for(int i=0, j=0; i<sb.length(); i++) {
            if(r > i && dp[(j = center*2 - i)]!=r-i+1) {

                dp[i] = Math.min(r-i+1, dp[j]);
            } else {
                for(j=1; i-j>-1 && i+j<sb.length() && sb.charAt(i-j)==sb.charAt(i+j); j++) ;
                if(i+j-1 > r) {
                    r = i+j-1;
                    center = i;
                }
                dp[i] = j;
                if(resultR < j) {
                    resultR = j;
                    resultC = i;
                }
            }
        }
        StringBuilder result = new StringBuilder(resultR-1);
        for(int i=resultC-resultR+1; i<resultR+resultC; i++) {
            if(sb.charAt(i) != '#') {
                result.append(sb.charAt(i));
            }
        }
        System.out.println(result.toString());
//        char[] result = new char[resultR-1];
//        result[resultC/2] = sb.charAt(resultC);
//        for(int i=1; i<resultR; i++) {
//            result[resultC/2-i] = result[resultC/2+i] = sb.charAt(resultC+2*i);
//        }
//        System.out.println(new String(result));
    }
}