[Swift 算法] 马拉车算法
|
提出问题原文：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，而且只存在一个独特的回文子串。 问题分析什么是回文字符串？
回文字符串有什么用？
算法对比在了解马拉车算法之前，我们有必要了解一下各种算法的优劣性，有助于我们对马拉车算法有更层次的了解。下面是关于回文串的四种算法对比：
马拉车算法我们从上面的表格，可以看到中心检测法其实已经是非常完善的了，但马拉车依然是技胜一筹，下面我们来看一下几个预处理。 预处理1：解决字符串长度奇偶问题马拉车算法可以看成是中心检测法的升级版本，在上面的表格中提到中心检测法是需要区分奇偶两种情况的，那么在马拉车算法中首先要解决的就是这个问题。 这里首先对字符串做一个预处理，在所有的空隙位置（包括首尾）插入同样的符号。无论原字符串是奇数还是偶数，通过这种做法，都会使得处理过的字符串变成奇数长度。 以插入#号为例： 123（长度为3） -> #1#2#3# （长度为7） abccba （长度为6）-> #a#b#c#c#b#a#（长度为13） 我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。 马拉车算法定义了一个回文半径数组 Len，用 Len[i] 表示以第 i 个字符为对称轴的回文串的回文半径。 我们来看看插入了
分割线所对应的 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 对称。所以这里有关系式 我们下面要去证明在
我想这个图已经说的很明白了吧 ??♂?，_middlePoint_ 的左右每个元素对应相等，回文长度为 证得： 在遍历过程的某个可能，j 对应的字符串突破 middlPoint 设立的围墙，见识到了墙外的世界，如下图所示：
此时我们无法再得到
重新匹配完之后可能是下面的这种情况，但无论 i 处的回文字符串长度有没有比 middlePoint 处的长度大，我们都需要更新 middlePoint 为 i，更新 rightMax 为 i 处回文串的右边界。
好的，那我们总结一下
第二种情况：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
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |