Manacher 算法

[Yhzhtk]

花了好长时间来看这个算法，网上有很多blog，写得都晦涩难懂。

好不容易找到这篇，简洁明了，图清晰，比较容易看懂，记录一下： http://blog.csdn.net/coraline_m/article/details/10002791

[Yhzhtk]

package info.yhzhtk.zlearn;

import java.util.Arrays;

/**
 * Manacher算法
 * 
 * @author gudh
 * @create 2016年5月1日
 */
public class Manacher {

    public static int manacher(char[] str) {
        // 原始数据处理
        char[] s = new char[str.length * 2 + 2]; // 多加前缀两个
        // 存储以下位字符为中心的最长回文串长度
        int[] rad = new int[str.length * 2 + 2];

        int len = str.length;
        int len1 = len << 1;

        // 初始化数组
        s[0] = '*';
        s[1] = '#';
        for (int i = 0; i < len; i++) {
            s[2 * i + 2] = str[i];
            s[2 * i + 3] = '#';
        }
        // abab变为*#a#b#a#b#

        int res = -1;
        for (int i = 2, j = 0, k = 0; i < len1;) {
            while (i + j + 1 < s.length && s[i - j - 1] == s[i + j + 1]) {
                j++; // 扫描得出rad
            }
            rad[i] = j;
            if (j > res) {
                res = j;
            }
            for (k = 1; k <= j && rad[i - k] != rad[i] - k; k++) {
                rad[i + k] = Math.min(rad[i - k], rad[i] - k);
            }
            i += k;
            j = Math.max(j - k, 0);
        }
        System.out.println(Arrays.toString(s));
        System.out.println(Arrays.toString(rad));
        System.out.println(Arrays.toString(str));
        return res;
    }

    public static void main(String[] args) {
        String str = "abababaabababcabc";
        System.out.println(manacher(str.toCharArray()));
    }

}

参照写的算法并测试，输出结果如下：

[*, #, a, #, b, #, a, #, b, #, a, #, b, #, a, #, a, #, b, #, a, #, b, #, a, #, b, #, c, #, a, #, b, #, c, #]
[0, 0, 1, 0, 3, 0, 5, 0, 7, 0, 5, 0, 3, 0, 1, 12, 1, 0, 3, 0, 5, 0, 5, 0, 3, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0]
[a, b, a, b, a, b, a, a, b, a, b, a, b, c, a, b, c]
12

仔细琢磨琢磨，这个算法真的很奇妙。如此简洁、如此高效！