KY的技术小站

Cpp creates world

0%

Manacher算法 -- LeetCode[5]

Posted on Edited on In

虽然LeetCode上这是一道Medium的题目，题目的解法有很多种。但是其中的最优解，也是本文需要探讨的算法，算是理解难度最高的一种。

拿到这个道题的第一反应，应该是从回文序列的对称中心向两侧看。算出以字符串中每一个字符为中心的最大回文串长度。然后取一个最长的，即为本题解。

在上述算法过程中，会有一部分算法的”冗余”。所谓算法冗余，即是对重复而无意义数据的计算。而Mangcher算法的优化就是去除了重复和无意义计算的部分。

说明：
1.Manacher算法的优化，其实是针对了具体的特殊“数据结构”而做的优化。做题的时候，也许可以从题中给出的特殊结构，来获取一些优化策略。本题中的特殊“数据结构”就是回文字符串。
2.在动态规划的思想中，dp[i]=fn(dp[i-n])，即当前的计算结果依赖之前某一次（这里没有说是上一次）已有的计算结果。
—–>而最长回文子序列的计算，则是综合了上两种思想。

与动态规划思想类似，从“通项公式”的角度来考虑。

假如我们已经有了 下标索引为 i-1 之前所有的计算结果。即 以 小于 i-1 索引的字符 为中心的回文子序列已经全部计算出来了。

如何计算i的值就是Manacher算法解决的问题

按照上面的说明，dp[i]=fn(dp[i-n])。那先看，第i个字符和小于i的某个字符的最长回文子序列有什么关系？

每个 i 都有以自己为中心的回文子序列，那么，把右边界最远的回文子序列称为最远序列。

第i个字符和这个 最远序列 有两种关系：

  1. 第i个字符在最远序列 内
  2. 第i个字符在最远序列 外

这里为什么要用最远序列？后文再解释。
如下图，m表示 小于i的某个字符的最长回文子序列

当前字符在最远回文序列的内部

在这种情况下，需要充分利用已有的回文序列的特征。

以下把索引i对应的字符 记作 c , 把当前最远回文序列记作s, 当前最远回文序列的中心点记为 si

c在一个已有的 s 内，那么根据回文序列的特点，必然还有一个字符关于这个 s 的中心点与c成轴对称。

那么在这个前提之下，在这个 s 内，如果以c为中心的是回文序列，那么对称点应该也是回文序列吧。

以下把 c 在 s 内的对称点记作 c’, c‘的索引计算为 si-(i-si) = 2*si - i
再仔细思考一下，还是需要分情况讨论。

1. 如果已计算出的 c’ 的最长回文序列的左边缘在 s 的左边缘内

dp[i] = dp[2*si-1]
也就是说，c 的最长回文子序列，就是c’的最长回文子序列。

条件一：c’ 和 c 轴对称 条件二：c’ 的最长回文子序列整个都在s内
由以上两个条件可以推出，以 c 和 c’ 为对称中心的回文子序列一样。

2. 如果已计算出的 c’ 的最长回文序列的左边缘在 s 的左边缘外

dp[i] = (i-si)*2+1

在这种情况下，c 的右边缘应该是紧贴 s 的右边缘。

想象一下， 如果 c 的右侧可以超出 s 的右边缘，那么 s 的最长回文子序列应该不止如此吧。
也就是说 c 的长度是 s 的瓶颈。

3. 如果已计算出的 c’ 的最长回文序列的左边缘在 s 的左边缘上

dp[i] = dp[2*si-i] + fn(si+1)

在这种情况下，以 c 为中心的回文子序列的最左边缘就不确定了,需要通过递增扩大右边缘来逐步确定以 c 为中心的最大子序列

当前字符在最远回文序列的外部

这个条件下只有一种情况，即 i = s 序列的右边缘 + 1。与上面的第三种情况一样，也是通过递增来寻找 以 c 为中心的 最大子序列。

注

  1. 在实际操作的时候，有些细节，例如把字符串间隔中插入#来避免奇偶问题（if else处理奇偶问题确实很蛋疼）。字符串的长度会变成 2*s+1.
  2. 在计算完成之后，需要再把#移除
  3. 这里解释一下，为什么要用最远序列，而不是前 i-1 回文序列。i-1并不一定是最远的，命中 i 在 i-1 的序列中概率不是很大。为了提高利用的<i关于某个中心的对称点>这一重复计算的概率，故用最远序列来处理。

细节是魔鬼，看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
func longestPalindrome(s string) string {
	fs := formatString(s)
	r := coreCal(fs)
	ret := cutString(r)
	return ret
}

//在字符串中插入#
func formatString(s string) []byte {
	c := byte('#')
	os := []byte(s)
	ns := make([]byte, 2*len(s)+1)
	ns[0] = c
	for index := 0; index < len(s)*2+1; index++ {
		if index%2 == 0 {
			ns[index] = c
		} else {
			ns[index] = os[index/2]
		}
	}

	return ns
}

//移除字符串中的 #
func cutString(s []byte) string {
	rs := make([]byte, len(s)/2)
	c := byte('#')
	for index := 0; index < len(s); index++ {
		if s[index] != c {
			rs[index/2] = s[index]
		}
	}

	return string(rs)
}

//计算最长回文子序列
func coreCal(fs []byte) []byte {
	// fs.len 是奇数
	dp := make([]int, len(fs))

	var longestString []byte

	rightEdge := -1
	si := 0

	for i := 0; i < len(fs); i++ {
		if i > rightEdge {
			pLen := deepFind(fs, i-1, i+1)

			si = i
			rightEdge = si + pLen/2

			if pLen > len(longestString) {
				longestString = fs[si-pLen/2 : si+pLen/2+1]
			}

			dp[i] = pLen
		} else {
			ii := 2*si - i //对称点
			iiLeft := ii - dp[ii]/2

			siLeft := si - dp[si]/2
			siRight := si + dp[si]/2

			if iiLeft > siLeft {
				dp[i] = dp[ii]
			} else if iiLeft < siLeft {
				dp[i] = 2*(siRight-i) + 1
			} else {
				pLen := deepFind(fs, 2*i-siRight-1, siRight+1)

				si = i
				rightEdge = si + pLen/2

				if pLen > len(longestString) {
					longestString = fs[si-pLen/2 : si+pLen/2+1]
				}

				dp[i] = pLen
			}
		}
	}

	return longestString
}

//从left=l,right=r开始向左右两侧寻找回文序列
func deepFind(fs []byte, l int, r int) int {
	for l >= 0 && r < len(fs) {
		if fs[l] != fs[r] {
			break
		}
		l--
		r++
	}

	return r - l - 1
}