Я не знаком с алгоритмом Манахера, но мне всегда нравилось разрабатывать эффективные алгоритмы, поэтому я решил попробовать это.

Ваш алгоритм определения того, является ли строка палиндромом, похож на тот, который придумал я, поэтому я решил просто использовать вашу функцию 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, оно выглядит как стандартная грубая сила, но простое и читаемое решение.

Моей первой мыслью о другом алгоритме также была довольно грубая сила, но это был совершенно другой подход, поэтому я называю его Наивным решением.

Идея наивного решения состоит в том, чтобы создать массивы подстрок исходной строки и проверить, является ли каждая подстрока палиндромом или нет. Способ, которым я определяю подстроки, состоит в том, чтобы начать с наибольшей возможной подстроки (исходной строки), а затем получить 2 подстроки длины string.length-1, а затем string.length-2 и так далее, пока, наконец, я не получу все подстроки длины 2 (я игнорирую подстроки длины 1, потому что вы сказали, что строка длины 1 не может быть палиндромом).

то есть: подстроки «теста», длина которых больше 1, будут:

["тест"] ["тес", "эст"] ["тэ", "эс", "ст"]

Таким образом, вы просто перебираете каждый из этих массивов и проверяете, являются ли они палиндромами, и увеличиваете количество, если они есть:

Наивное решение:

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
    }
}

Я прекрасно знал, что этот алгоритм будет медленным, но я хотел реализовать его в качестве второго базового уровня для моего реального решения.

Я называю это решение умным решением. Это многопроходное решение, использующее преимущества количества и позиций символов в строке.

В первом проходе я генерирую то, что я называю отображением символов. Отображение символов — это словарь, который отображает Character в массив индексов. Таким образом, вы просматриваете строку и добавляете индекс каждого символа в массив, хранящийся под его символьным значением в качестве ключа.

Идея состоит в том, что палиндромы могут существовать только в строке, которая заканчивается одной и той же буквой. Поэтому вам нужно только проверять подстроки внутри строки по индексам конкретной буквы. В слове «татуировка» у вас 3 разные буквы: «т», «а», «о». Сопоставление символов будет выглядеть так:

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 подстроки. Это идея. И как только вы проверили все возможные подстроки, заканчивающиеся определенной буквой, вы можете игнорировать любые другие найденные подстроки, начинающиеся с этой буквы, потому что вы уже проверили их.

Во втором проходе я просматриваю каждый символ в строке, и если я еще не проверил эту букву, я просматриваю пары индексов перестановки, сгенерированные generateOrderedPairIndexPermutations для индексов в сопоставлении символов и проверьте подстроки, чтобы увидеть, являются ли они палиндромом. Затем я делаю 2 оптимизации здесь. Во-первых, если расстояние между индексом начального символа и индексом конечного символа меньше 3, это должен быть палиндром (расстояние 1 означает, что они следуют друг за другом, а расстояние 2 означает, что между ними находится одна буква, поэтому также гарантированно будет палиндромом). Во-вторых, поскольку я уже знаю, что первый и последний символы совпадают, мне не нужно проверять всю подстроку, только от второй буквы до предпоследней буквы. Итак, если подстрока будет «тест», и я всегда гарантирую себе, что подстрока зарезервирована одной и той же буквой, мне на самом деле не нужно проверять «тест», и вместо этого я могу просто проверить «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 для измерения производительности, я прогнал каждый алгоритм через несколько тестов производительности. Используя эту строку в качестве основного источника: "Здесь несколько палиндромов""Что я видел, машину или кошку", обновлено на основе предложений использовать более строгую входную строку< /strong>, длина которого составляет 3319 символов, если убрать пробелы и написать строчными буквами ("здесь есть несколько палиндромов""wasitacaroracatisaw"< /strong>), я также создал копии, в которых эта строка повторялась дважды ("therearemultiplepalindromesinheretherearmultiplepalindromesinhere"wasitacaroracatisawwasitacaroracatisaw), 4 раза, 8 раз и 10 раз. попытка определить O () алгоритма, увеличение количества букв и измерение коэффициента масштабирования - это путь.