//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
}
}
马拉车算法
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
