Manacher(马拉车算法）

算法原理

• example: str = "a film called tenet"

• 寻找最长回文串的一般解法(暴力)
  对于字符串中的每一个字符 进行中心拓展
  伪代码 时间复杂度O(n^2)

    for(int i=0;i<len;++i){
     int l=r=i,tmp=-1;
     while(l>=0&&r<len&&str[l--]==str[r++]){
         tmp+=2;}//字符串长度为奇数
     ans=tmp>ans?tmp:ans;
     l=i,r=i+1,tmp=0;
     while(l>=0&&r<len&&str[l--]==str[r++]){
         tmp+=2;}//字符串长度为偶数
     ans=tmp>ans?tmp:ans;
    }
  

• 马拉车算法流程如下

• 预处理
  先在字符串开头与结尾插入两个不同的特殊字符
  再在字符之间插入特殊符号
  如：" ^#a# #f#i#l#m# #c#a#l#l#e#d# #t#e#n#e#t#$ "
  将字符串转换为奇数长度进行统一处理,首尾不同的符号帮助边界判断

• 算法核心
  在暴力的同时,最大化利用已有信息,对后续操作提供加速
  流程如下 :

  • 以每个字符为中心进行回文半径计算

    str	^	#	t	#	e	#	n	#	e	#	t	#	$
    raduis		1	2	1	2	1	6	1	2	1	2	1
    location	0	1	2	3	4	5	6	7	8	9	10	11	12

  • 这里raduis用于记录对应位置的回文半径

    把目光放在str[6] 这里计算出半径为6 (记center=6)
    可以知道指针在运算时实际已经处理到了0和10的位置 (记最前位置R=12)
    一般暴力操作是以下个字符str[7]为中心继续向两端进行匹配拓展
    而马拉车进行的优化就是在这里
    对于str[7] 7<12 断言raduis[7]=raduis[5]=1
    对于str[8] 7<12 断言raduis[8]=raduis[4]=2

  • 分析

    	5	4	3	2	1	0
    	#	e	#	t	#	^
    n
    	#	e	#	t	#	$
    	7	8	9	10	11	12

    a.由对称性str[5]_{str[1]和str[7]}str[11]是相同的两段
    当计算raduis[7]和radius[8]时我们会注意它们和
    对称的raduis[5]和radius[4]“大致”相同
    仔细发现str[4]的回文串部分str[5]~str[3]
    是包含在str[6]的回文串部分str[1]~str[11]的
    而又由str[6]位置的回文性质(a.) 可以知道str[4]的回文串部分会对应在str[8]左右
    即str[5]_{str[3]对应到str[7]}str[9]
    从而可以得到raduis[8]=raduis[4]
    这就是马拉车算法用到的思想

  • 其他情况的考虑

    刚才是对应位置的回文串部分被包含在一个大的回文串里
    即str[i]的 对应位置回文半径长 raduis[2C-i] + i < R (R是已知回文串最右位置)
    对于raduis[2C-i] + i >= R 我们不知道溢出的部分 是否能匹配上
    但可以知道至少有str[i]~ str[R]这一部分是对称的
    也就是说raduis[i]数值上至少等于R - i
    于是我们可以直接从溢出部分开始进行字符串比较

  • 综合考虑

    当正在计算的位置 i < R 的时候可以优化
    raduis[2C-i] < R - i 的时候 raduis[i] = raduis[2C-i]
    raduis[2*C-i] >= R - i 则raduis[i] = R - i 再从最远端位置R继续匹配

  • 关于回文串返回

    str	^	#	t	#	e	#	n	#	e	#	t	#	$
    raduis		1	2	1	2	1	6	1	2	1	2	1
    location	0	1	2	3	4	5	6	7	8	9	10	11	12

    1. 原回文串的长度 len = raduis[i] - 1

       这里不是巧合
       raduis[i]*2-1得到预处理后的回文串长度 总是奇数
       对应的回文串只有两种形式

       • #x#x# 原回文串长度为偶数
       • #x#x#x# 原回文串长度为奇数

       但不管如何'#'的个数总是比处理字符多1
       (raduis[i] * 2 - 1 - 1) / 2得到正确长度

    2. 原回文串开始位置(包含) start = (i - raduis[i]) / 2
       index/2得到原字符串位置+1的地方
       i-radius[i]得到预处理串开始位置(不包含)
       (i-radius[i])/2 得到原字符串开始位置(包含)

代码实现

class solution {
    String manacher(String s) {
        if (s.isEmpty()) {
            return "";
        }
        StringBuilder builder = new StringBuilder("^#");
        for (char c : s) {
            builder.append('c');
            builder.append('#');
        }
        builder.append('$');
        char[] str = builder.toString().toCharArray();
        int len = str.length;
        int[] raduis = new int[len];
        int C = -1, R = -1;
        int ans = 0;
        for (int i = 1; i < len - 1; ++i) {
            raduis[i] = i > R ? 1 : Math.max(R - i, raduis[2 * C - i]);
            while (str[i - raduis[i]] == str[i + raduis[i]]) {
                ++raduis[i];
            }
            if (raduis[i] > raduis[ans]) {
                ans = i;
            }
            if (i + raduis[i] > R) {
                R = i + raduis[i];
                C = i;
            }
        }
        int len = raduis[ans] - 1;
        int start = (ans - raduis[ans]) / 2;
        return s.subString(start, start + len);
    }
}