[Swift 算法] 马拉车算法

本算法原名为 Manacher 算法，是为了解决 “找出字符串的最长回文子串” 这个问题而提出，该问题收录在 LeetCode 【Longest Palindromic Substring】中。

提出问题

原文：Given a string S,find the longest palindromic substring in S. You may assume that the maximum length of S is 1000,and there exists one unique longest palindromic substring.

译文：给出一个字符串 S，找到在 S 中的最长的回文子串。你可能需要假设 S 的最大长度为 1000，而且只存在一个独特的回文子串。

问题分析

什么是回文字符串？

如果一个字符串正着读和反着读是一样的，就称它为回文字符串。例如 121，abccba 等。

回文字符串有什么用？

可以用来写诗，例如苏轼的 《菩萨蛮》?

落花闲院春衫薄，薄衫春院闲花落。迟日恨依依，依依恨日迟。梦回莺舌弄，弄舌莺回梦。邮便问人羞，羞人问便邮。

算法对比

在了解马拉车算法之前，我们有必要了解一下各种算法的优劣性，有助于我们对马拉车算法有更层次的了解。下面是关于回文串的四种算法对比：

算法种类	时间复杂度	空间复杂度	简述
暴力枚举法	O(N³)	O(N³)	遍历所有子字符串，子串数为 N²，长度平均为 N/2
动态规划法	O(N²)	O(N²)	两层循环，外层循环从后往前扫，内层循环从当前字符扫到结尾处，省略已经判断过的记录
中心检测法	O(N²)	O(1)	分奇偶两种情况，以 i 为中心不断向两边扩展判断，无需额外空间
马拉车算法	O(N)	O(N)	从左到右扫描，省略已经判断过的记录，线性

马拉车算法

我们从上面的表格，可以看到中心检测法其实已经是非常完善的了，但马拉车依然是技胜一筹，下面我们来看一下几个预处理。

预处理1：解决字符串长度奇偶问题

马拉车算法可以看成是中心检测法的升级版本，在上面的表格中提到中心检测法是需要区分奇偶两种情况的，那么在马拉车算法中首先要解决的就是这个问题。

这里首先对字符串做一个预处理，在所有的空隙位置（包括首尾）插入同样的符号。无论原字符串是奇数还是偶数，通过这种做法，都会使得处理过的字符串变成奇数长度。

以插入#号为例：

123（长度为3） -> #1#2#3# （长度为7）

abccba （长度为6）-> #a#b#c#c#b#a#（长度为13）

我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。

马拉车算法定义了一个回文半径数组 Len，用 Len[i] 表示以第 i 个字符为对称轴的回文串的回文半径。

我们来看看插入了#字符后的 Len 数组内数据是怎么计算的吧：

分割线所对应的 index 为 i 的字节的实际回文长度明显为 2Len[i] - 1 ? 好的，这样我们就完成了第一步预处理，下面我们进行第二步的预处理 ? 。

预处理2：解决遍历过程可能出现的数组越界

涉及到遍历，数组越界问题，一直都很让人头疼 ?，在这个算法中我们同样会遇到这样的问题：

为了解决这个问题，我们或许可以像下面这样做一大堆的判断：

if ... {
    if ... {
        
    } else {
        
    }
} else {
    if ... {
            
    } else {
                
    }
}

又或许我们可以在字符串的首尾处各加入一个字符，例如 ~ 和 +，只要两个字符不相同，就没有可能成为最长字符串的一部分，不会对我们的结果造成影响，看下面 ? ：

123（长度为3） -> ~#1#2#3#+ （长度为9）

abccba （长度为6）-> ~#a#b#c#c#b#a#+（长度为15）

再加上下面的图片，可能可以更容易明白：

用不匹配的结果来代替程序崩溃，十分划算。

预处理的代码如下：

// 存储字节的数组
var charactersArr = Array<Character>()

charactersArr.append("~")
// s为输入的字符串
for character in s.characters {
     charactersArr.append("#")
     charactersArr.append(character)
}
charactersArr.append("#")
charactersArr.append("+")

IntPut: "123"

OutPut: ["~","#","1","2","3","+"]

这样我们就做完了所有的预处理，下面我们来看一下这个算法是怎么优化运算过程的 ?

思路分析

我们现在的问题已经变成怎么高效的求出 Len 数组中所有的值，而当最后取得数组中最大的值后，最长的回文字符串也就呼之欲出了。

属性设置：_middlePoint_ 和 rightMax

我们首先设立两个值，_rightMax_ 和 middlePoint_，_middlePoint 为有效的中心点，而 rightMax 为 middlePoint 对应的回文字符串的右边界。它们的位置关系如下图所示：

middlePoint 的位置并不是不变的，在从左到右的遍历过程中，_middlePoint_ 的位置会根据 i 与 rightMax 和 Len[i] 的关系进行变化。

在从左到右遍历的过程中，我们会需要求出每一个 i 对应的回文字符串长度，那么通常会出现有些 i 的回文长度较短，被包括在之前的较长的回文字符串中，如果这个 i 的回文长度我们可以通过之前的数组中的某些值来求出，那么岂不是很便利？

这就要求我们来找出 Len 数组中的值的各种关系。

Len 数组计算

第一种情况：i <= rightMax

在上图中，i 和 j 对应的两个子回文串被 middlePoint 对应的回文串完全包括。

这里我们姑且将 middlePoint 当作一个我们已知最长回文串的一个中心点。而 j 是我们前面已经求过的某个点，它的特点是与我们要去求的 i 根据 middlePoint 对称。所以这里有关系式 2 * middlePoint - i 。

我们下面要去证明在 i <= rightMax 的前提下 Len[i] = Len[j]，?看?下面的图：

我想这个图已经说的很明白了吧 ?‍♂️，_middlePoint_ 的左右每个元素对应相等，回文长度为 2Len[middlePoint] - 1，而 j 点左右元素对应相等，回文长度为 2Len[j] - 1，这意味着 i 点处左右元素也会对应相等，且回文长度为 2Len[j] - 1。

证得：Len[i] == Len[j]。好，我们继续。

在遍历过程的某个可能，j 对应的字符串突破 middlPoint 设立的围墙，见识到了墙外的世界，如下图所示：

此时我们无法再得到 Len[i] == Len[j] 这个结论，我们在 i 处只能选择去除墙外的那部分，并重新进行匹配。

重新匹配完之后可能是下面的这种情况，但无论 i 处的回文字符串长度有没有比 middlePoint 处的长度大，我们都需要更新 middlePoint 为 i，更新 rightMax 为 i 处回文串的右边界。

好的，那我们总结一下 i<= rightMax 这种情况下的 Len 数组计算。

Len[i] == Len[2 * middlePoint - i]

Len[i]（有效）== min(rightMax - i,Len[2 * middlePoint - i])
匹配前或者匹配后，出现 Len[i] > rightMax，需要更新 middlePoint 和 rightMax

第二种情况：i > rightMax

这种情况下，i 并不在 middlePoint 的回文串范围内，也就无法省略部分的匹配步骤，只能重新匹配。匹配完毕之后，同样需要更新 middlePoint 和 _rightMax_。

下面是完整的 Swift 实现代码：

//Manacher's Algorithm (马拉车算法)
    class func longestPalindrome_ma(s: String) -> String {
        var charactersArr = Array<Character>()
        var resultString = String()
        var maxPoint = 0
        
        charactersArr.append("$")
        for character in s.characters {
            charactersArr.append("#")
            charactersArr.append(character)
        }
        charactersArr.append("#")
        charactersArr.append("%")
        
        var rightMax = 0,middlePoint = 0
        var lenArr = Array.init(repeating: 1,count: charactersArr.count)
        
        for i in 1 ..< 2 * s.characters.count + 2 {
            if rightMax > i {
                lenArr[i] = min(rightMax - i,lenArr[2 * middlePoint - i])
            }
            
            while charactersArr[i - lenArr[i]] == charactersArr[i + lenArr[i]] {
                lenArr[i] += 1
            }
           
            if lenArr[i] + i > rightMax {
                middlePoint = i
                
                rightMax = lenArr[i] + i
            }
            
            if lenArr[i] > lenArr[maxPoint] {
                maxPoint = i
            }
        }
        
        for i in stride(from: maxPoint - (lenArr[maxPoint] - 2),to: maxPoint + (lenArr[maxPoint] - 1),by: 2) {
            resultString.append(charactersArr[i])
        }
        
        return resultString
    }
}

下一篇文章是 KMP 算法，如果感兴趣，请点击 star 支持。另欢迎加入我，一起玩才开心。