Оптимизация поиска по диапазону строк

Question

В настоящее время я работаю над алгоритмом для поиска всех диапазонов целевой строки.

Пример:

Input: s = "acfacfacf", target = "acf"
Output: [(0, 3), (3, 6), (6, 9)]
Note: the upperBound is not an index of the subarray.

Это мое текущее решение:

extension String {
    func allRanges(of string: String) -> [(Int, Int)] {

        var ranges = [(Int, Int)]()
        var set: Set<Int> = []
        let chars = Array(self)
        let target = Array(string)

        for index in 0..<chars.count {
            if chars[index] == string.first { set.insert(index) }
            for i in set {
                if index-i < target.count && chars[index] == target[index-i] {
                    if index-i == target.count-1 {
                        ranges += [(i, index+1)]
                    }
                } else {
                    set.remove(i)
                }
            }
        }

        return ranges
    }
}

Этот алгоритм хорошо работает со строками типа «acfacfacf», но плохо работает со строками типа «аааааааааааааааа», где целью является «аааааааа», и ожидаемый результат:

[(0, 8), (1, 9), (2, 10), (3, 11), (4, 12), (5, 13), (6, 14), (7, 15), (8, 16), (9, 17)]

Есть ли какие-либо оптимизации, которые можно сделать здесь?

Изменить: Также. Я понимаю, что использование кортежей здесь не очень похоже на Swifty, но это не самая большая моя проблема.

Answer 1

Вы можете перебирать индексы своей коллекции, удаляя последние n элементов (размер вашей коллекции минус один), проверьте, равны ли элементы подпоследовательности другой коллекции, если true, верните диапазон, иначе верните nil:

extension Collection where Element: Equatable {
    func indices<C: Collection>(of collection: C) -> [Index] where C.Element == Element {
        let size = collection.count
        return indices.dropLast(size-1).filter {
            self[$0..<index($0, offsetBy: size)].elementsEqual(collection)
        }
    }
    func ranges<C: Collection>(of collection: C) -> [Range<Index>] where C.Element == Element {
        let size = collection.count
        return indices.dropLast(size-1).compactMap {
            let range = $0..<index($0, offsetBy: size)
            return self[range].elementsEqual(collection) ? range : nil
        }
    }
}

---

---

Вы также можете попытаться оптимизировать его, используя метод коллекции starts(with:), чтобы избежать смещения индекса коллекции на каждой отдельной итерации:

func starts<PossiblePrefix>(with possiblePrefix: PossiblePrefix) -> Bool where PossiblePrefix : Sequence, Self.Element == PossiblePrefix.Element

---

extension Collection where Element: Equatable {
    func ranges<C: Collection>(of collection: C) -> [Range<Index>] where C.Element == Element {
        let size = collection.count
        return indices.dropLast(size-1).compactMap {
            self[$0...].starts(with: collection) ? $0..<index($0, offsetBy: size) : nil
        }
    }
}

---

---

Или застегнуть нижний и верхний индексы возможных диапазонов:

extension Collection where Element: Equatable {
    func ranges<C: Collection>(of collection: C) -> [Range<Index>] where C.Element == Element {
        let k = collection.count-1
        return zip(indices.dropLast(k),indices.dropFirst(k)).compactMap {
            self[$0...].starts(with: collection) ? $0 ..< index(after: $1) : nil
        }
    }
}

Answer 2

Строительство из поста Лео. Кажется, есть какая-то ненужная работа с выполнением .start(...), а затем index(...). Это может быть дополнительно оптимизировано с помощью

extension Collection where Element: Equatable {

    func ranges<C: RandomAccessCollection>(of collection: C) -> [Range<Index>] where C.Element == Element {
        let size = collection.count
        return indices.dropLast(size-1).compactMap { idx in
            var i = idx
            var match = false
            collection.drop { element in
                match = element == self[i]
                i = index(after: i)
                return match
            }
            return match ? idx..<i : nil
        }
    }
}