我不熟悉 Manacher 的算法，但我一直很喜欢找出有效的算法，所以我想我会尝试一下。
您确定字符串是否为回文的算法看起来像我想出的那种，所以我决定只使用您的isPalindrome函数，尽管我将其更改为扩展的函数String，并且我删除了空格删除逻辑，因为我觉得需要在调用调用中而不是在回文确定函数本身中。
extension String {
func isPalindrome() -> Bool {
if length < 2 { return false }
let str = lowercased()
let strArray = Array(str.characters)
var i = 0
var j = strArray.count-1
while i <= j {
if strArray[i] != strArray[j] { return false }
i+=1
j-=1
}
return true
}
}
查看您的palindromsInString解决方案后，它看起来像是一个标准的蛮力，但简单易读的解决方案。
我对不同算法的第一个想法也是相当蛮力的，但这是一种完全不同的方法，所以我称它为 Naive 解决方案。
Naive 解决方案的想法是创建原始字符串的子字符串数组，并检查每个子字符串是否为回文。我确定子字符串的方法是从可能的最大子字符串（原始字符串）开始，然后得到 2 个长度的子字符串string.length-1，然后string.length-2依此类推，直到最后我得到所有长度为 2 的子字符串（我忽略了长度 1 因为你说长度为 1 的字符串不能是回文）。
即：“test”的子串大于长度 1 将是：
["test"] ["tes", "est"] ["te", "es", "st"]
因此，您只需遍历每个数组并检查是否有回文，如果是则增加计数：
天真的解决方案：
extension String {
var length: Int { return characters.count }
func substringsOfLength(length: Int) -> [String] {
if self.length == 0 || length > self.length { return [] }
let differenceInLengths = self.length - length
var firstIndex = startIndex
var lastIndex = index(startIndex, offsetBy: length)
var substrings: [String] = []
for _ in 0..<differenceInLengths {
substrings.append(substring(with: Range(uncheckedBounds: (firstIndex, lastIndex))))
firstIndex = index(after: firstIndex)
lastIndex = index(after: lastIndex)
}
substrings.append(substring(with: Range(uncheckedBounds: (firstIndex, lastIndex))))
return substrings
}
}
extension String {
func containsAPalindromeNaive(ignoringWhitespace: Bool = true) -> Int {
let numChars = length
if numChars < 2 { return 0 }
let stringToCheck = (ignoringWhitespace ? self.components(separatedBy: .whitespaces).joined(separator: "") : self).lowercased()
var outerLoop = numChars
var count: Int = 0
while outerLoop > 0 {
let substrings = stringToCheck.substringsOfLength(length: outerLoop)
for substring in substrings {
if substring.isPalindrome() {
count += 1
}
}
outerLoop -= 1
}
return count
}
}
我很清楚这个算法会很慢，但我想将它作为我真正解决方案的第二个基线来实现。
我将此解决方案称为智能解决方案。它是一种利用字符串中字符的数量和位置的多通道解决方案。
在第一遍中，我生成了我所说的字符映射。字符映射是将 a 映射Character到索引数组的字典。因此，您遍历字符串并将每个字符的索引添加到存储在其字符值下作为键的数组中。
这个想法是回文只能存在于以相同字母结尾的字符串中。因此，您只需要在特定字母的索引处检查字符串中的子字符串。在“纹身”这个词中，你有 3 个不同的字母：“t”、“a”、“o”。字符映射如下所示：
t: [0,2,3]
a: [1]
o: [4,5]
我现在知道回文只能存在于这个词中（0,2）、（2,3）和（4,5）之间。所以我只需要检查 3 个子字符串(0,2)、(0,3)、(2,3) 和 (4,5)。所以我只需要检查 4 个子字符串。这就是想法。一旦您检查了所有可能的以特定字母结尾的子字符串，您就可以忽略遇到的以该字母开头的任何其他子字符串，因为您已经检查过它们。
在第二遍中，我遍历字符串中的每个字符，如果我还没有检查那个字母，我会遍历由for生成的排列索引对generateOrderedPairIndexPermutations字符映射中的索引并检查子字符串以查看它们是否为回文。然后我在这里做了 2 次优化。首先，如果起始字符索引和结束字符索引之间的距离小于 3，则它必须是回文（距离 1 表示它们是连续的，距离 2 表示它们之间只有一个字母，因此也保证是回文）。其次，因为我已经知道第一个字符和最后一个字符是相同的，所以我不需要检查整个子字符串，只需从第二个字母到倒数第二个字母。因此，如果子字符串是“test”，并且我总是保证子字符串以相同的字母结尾，我实际上不需要检查“test”，而我可以只检查“es”。它'
智能解决方案：
extension Collection {
func generateOrderedPairIndexPermutations() -> [(Index,Index)] {
if count < 2 {
return []
}
var perms: [(Index,Index)] = []
var firstIndex = startIndex
while firstIndex != endIndex {
var secondIndex = index(firstIndex, offsetBy: 1)
while secondIndex != endIndex {
perms.append((firstIndex,secondIndex))
secondIndex = index(secondIndex, offsetBy: 1)
}
firstIndex = index(firstIndex, offsetBy: 1)
}
return perms
}
}
extension String {
func generateCharacterMapping() -> [Character : [Int]] {
var characterMapping: [Character : [Int]] = [:]
for (index, char) in characters.enumerated() {
if let indicesOfChar = characterMapping[char] {
characterMapping[char] = indicesOfChar + [index]
} else {
characterMapping[char] = [index]
}
}
return characterMapping
}
func containsAPalindromeSmart(ignoringWhitespace: Bool = true) -> Int {
let numChars = length
if numChars < 2 { return 0 }
let stringToCheck = (ignoringWhitespace ? self.components(separatedBy: .whitespaces).joined(separator: "") : self).lowercased()
let characterMapping = stringToCheck.generateCharacterMapping()
var count: Int = 0
var checkedChars: Set<Character> = Set()
for char in stringToCheck.characters {
if checkedChars.contains(char) == false {
if let characterIndices = characterMapping[char], characterIndices.count > 1 {
let perms = characterIndices.generateOrderedPairIndexPermutations()
for (i,j) in perms {
let startCharIndex = characterIndices[i]
let endCharIndex = characterIndices[j]
if endCharIndex - startCharIndex < 3 {
count += 1
} else {
let substring = stringToCheck.substring(with: Range(uncheckedBounds: (stringToCheck.index(stringToCheck.startIndex, offsetBy: startCharIndex+1), stringToCheck.index(stringToCheck.startIndex, offsetBy: endCharIndex))))
if substring.isPalindrome() {
count += 1
}
}
}
checkedChars.insert(char)
}
}
}
return count
}
}
我对这个解决方案感觉很好。但我不知道它到底有多快。真的很快_
使用 XCTest 来衡量性能，我通过一些性能测试运行了每个算法。使用此字符串作为基本来源：“这里有多个回文” “我看到的是汽车还是猫”，根据建议更新以使用更严格的输入字符串，删除空格后长度为33 19 个字符并且它是小写的（“ therearemultiplepalindromesinhere”“wasitacaroracatisaw”），我还创建了这个字符串乘以 2 的副本（“therearemultiplepalindromesinheretheraremultiplepalindromesinhere” wasitacaroracatisawwasitacaroracatisaw)、4 倍、8 倍和 10 倍。由于我们试图确定算法的 O()，因此按比例放大字母数量并测量比例因子是可行的方法。
为了获得更准确的数据，我将每个测试运行了 10 次迭代（我本来希望进行更多迭代，但是原始解决方案和我的 Naive 解决方案都没有在 4 次以上的测试中及时完成）。这是我收集的计时数据（电子表格的屏幕截图比在这里再次输入要容易）：
更新
更新
绿色是作者；红色是朴素的解决方案；橙色是智能解决方案
如您所见，您的原始解决方案和我的朴素解决方案都在二次时间中运行（您的解决方案的二次相关系数为 r=0.9997，而我的朴素解决方案的系数为 r=0.9999；所以，很明显是二次的！）。我的 Naive 解决方案似乎在您的解决方案之下，但它们都呈二次方增加，因此我们已经知道 O(n^2)。
我的智能解决方案的有趣之处在于它看起来是线性的！我通过回归计算器设置的 5 点小数据集，其相关系数为 r=0.9917！因此，如果它不是线性的，那么它是如此接近以至于我不在乎。
现在所有的解决方案都在二次时间中运行。乐叹息。但至少这个错误被发现，解决了，科学在今天占了上风。可惜我的“智能解决方案”实际上并不是线性的。但是，我会注意到，如果输入字符串还不是一个巨大的回文串（就像我最终将其更改为的那个），那么“智能解决方案”的优化使它执行得更快，尽管仍然是二次时间.
我不知道我的算法是否比 Manacher 的算法更容易理解，但我希望我能解释清楚。结果非常有希望，所以我希望你能从中找到一个很好的用途。这实际上仍然是正确的。我认为这是一个很有前途的算法。也许我的代码generateOrderedPairIndexPermutations不是最好的。
更新以解决 kraskevich 发现的错误