Manacher 算法：求最长回文子串

网络上关于最长回文子串的文章很多，这里只是为了记录一下思路与过程。

概述

manacher算法是一个高效的寻找最长回文子串的算法，时间复杂度和空间复杂度均为$O(n)$，相比于朴素算法有很高的优势。它利用了回文串镜像对称的性质，通过不断（间接）记录以每一个字符为中心的回文串长度，找到最大的回文子串。

回文串

定义

回文串，就是对称的串。比如：aba，abcba。最大回文子串，就是一个字符串中存在一个子串，使得它的长度是所有回文子串中最长的。例如：abcbac最长的，abcba，长度为5，是最大的回文子串。

为了方便讨论，我们假设总字符串为$S$, 回文串为$s$, 对于一个回文串，定义：

s.center # 回文串的中心位置，暂不区分奇偶
s.st     # 回文串开始的位置
s.nd     # 回文串结束的位置
s.mx     # 在s.center右方，离s.center最远的下标

性质

对称性

对称，最基本的特性。str = abcba，那么str[i] == str[len(str)-i-1]。就是，第一个a和最后一个a，第二个b和倒数第二个b，都跟串的中心，c，对称。

推论

在一个回文串$s, s.size == n$中，若以i为中心的字符串a[i]（i != s.center），是一个回文串，那么，对应的s的中心对称的位置也是一个回文串。

e.g.:

str = "a b a a b a"

在str中，若以str[1]为中心，可以得到一个回文串aba。在str[1]以str.center对称的位置上，str[4]也是一个回文串，aba.

这幅图阐述了这个性质。以id为中心，mx为边界，是一个回文串。同时，以j为中心存在一个回文串$s_1$。那么，以id对称的位置，也会有一个一样的字符串$s_2$存在。i就是这个串的中心。

然而，并非i处的回文串一定和j处的相同。有可能会有更长的情况，但这种情况只在i出现，不在j出现，于是乎需要从原始的$s_2$边界开始，向外搜索，就可以得到以i为中心的最长串。

算法设计

利用这写特性，我们来设计算法：
go的代码实现：

// min 求两个int的最小值
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// longestPalindrome 主要函数
func longestPalindrome(s string) string {
	var buf bytes.Buffer // 用来拼接字符串的buffer
	// predo
	for i := 0; i < len(s); i++ {
		buf.WriteByte('#')
		buf.WriteByte(byte(s[i]))
	} 
	buf.WriteByte('#')
    // 给字符串每一个字符之间加一个#，例如：
    // abcbac，--> #a#b#c#b#a#c#
    // 这样做的好处是，无论原来的字符串是奇数串还是偶数串，
    // 都可以格式化为奇数串，这样s.center就不会是一个
    // 的间隙 

	format := buf.String()
	p := make([]int, len(format))
	center, mx := 0, 0
	for i := 1; i < len(format); i++ {
		if i < mx {
			p[i] = min(mx-i, p[2*center-i])
		} else {
			p[i] = 1
		}
		for i-p[i] >= 0 && i+p[i] < len(format) && format[i+p[i]] == format[i-p[i]] {
			p[i] += 1
		}
		if mx-center < p[i] {
			mx = i + p[i]
			center = i
		}
	}

	var resBuf bytes.Buffer
	st := center - (p[center] - 1)
	for i := st; i < p[center]+center; i++ {
		if format[i] != '#' {
			resBuf.WriteByte(format[i])
		}
	}
	return resBuf.String()
}

实现步骤

预处理：转换为奇字符串

对字符串$S$，利用#填充字符之间的空隙，以达到将其转换为奇数串的目的。这样的好处是，任意下标的字符串都是一个奇数串，中心是可以由下标确定的，而不是像abba这样，中心在间隙中。
证明：任意串s，设 l = s.length()，那包括两端，l的间隙包含l+1个空位。那么，填充之后的字符串$S’$就包含$2l+1$个字符，是一个奇串。即使存在偶数回文串，那也可以以#为中心向两端扩张搜索。
e.g.:

s = "abcdcbac"
s1 = "#a#b#c#d#c#b#a#c#"
// center == s1[7] == 'd'

s = "abbac"
s1 = "#a#b#b#a#c#"
// center == s1[4] == '#'

回文串搜索

Manacher算法的基础步骤是，从头到尾，以每一个字符为中心，向两端搜索，以获得最大的回文子串的中心点及边界。在这个基础上，算法还记录每个下标的字符所拥有的最长子串从中心到边界的长度。也就是说，存在标记mx，右边界，center，中心，p []int, 每个下标对应的回文子串长度。例如：

init:
mx = 0 // 最大回文子串的最右边界：0为初始值
center = 0 // 最大回文子串的中心，0 init
s1 = "#a#b#c#b#a#c#" // 处理过的字符串

// 用于记录每一个下标对应的最大子串
p = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

iterate:
for i := 1; i < len(s1); i++ {
    if i < mx {
         p[i] = min(mx-i, p[2*center-i])
    } else {
        p[i] = 1
    }
    // 若i，即当前中心在回文串里时，有可能以这个中心包含一个回文串，
    // 那么这个中心的最大偏移数就是对称点的最大偏移数；
    for i-p[i] >= 0 && i+p[i] < len(format) && format[i+p[i]] == format[i-p[i]] {
        p[i] += 1
    }
    // 从基础值开始，寻找在最大偏移外部的串
    
    if mx-center < p[i] {
        mx = i + p[i]
        center = i
    }
    // 记录最大的回文串
}

通过这三个步骤，最终得到最大子串的中心和边界，这样就可以从中过滤出最大回文子串了。