Optimizing a String Range Search
Andrew
116

Hey,

I am currently working on an algorithm to find all ranges of a target string.

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

This is my current solution:

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

This algorithm does well on strings like "acfacfacf" but does poorly on strings like "aaaaaaaaaaaaaaaaa" where the target is "aaaaaaaa". Are there any optimizations that can be done here? Thanks.

Comments (0)