Swift find all occurrences of a substring

Question

I have an extension here of the String class in Swift that returns the index of the first letter of a given substring.

Can anybody please help me make it so it will return an array of all occurrences instead of just the first one?

Thank you.

extension String {
    func indexOf(string : String) -> Int {
        var index = -1
        if let range = self.range(of : string) {
            if !range.isEmpty {
                index = distance(from : self.startIndex, to : range.lowerBound)
            }
        }
        return index
    }
}

For example instead of a return value of 50 I would like something like [50, 74, 91, 103]

Answer 1

I know we aren't playing code golf here, but for anyone interested in a functional style one-line implementation that doesn't use vars or loops, this is another possible solution:

extension String {
    func indices(of string: String) -> [Int] {
        return indices.reduce([]) { $1.encodedOffset > ($0.last ?? -1) && self[$1...].hasPrefix(string) ? $0 + [$1.encodedOffset] : $0 }
    }
}

Answer 2

There's not really a built-in function to do this, but we can implement a modified Knuth-Morris-Pratt algorithm to get all the indices of the string we want to match. It should also be very performant as we don't need to repeatedly call range on the string.

extension String {
    func indicesOf(string: String) -> [Int] {
        // Converting to an array of utf8 characters makes indicing and comparing a lot easier
        let search = self.utf8.map { $0 }
        let word = string.utf8.map { $0 }

        var indices = [Int]()

        // m - the beginning of the current match in the search string
        // i - the position of the current character in the string we're trying to match
        var m = 0, i = 0
        while m + i < search.count {
            if word[i] == search[m+i] {
                if i == word.count - 1 {
                    indices.append(m)
                    m += i + 1
                    i = 0
                } else {
                    i += 1
                }
            } else {
                m += 1
                i = 0
            }
        }

        return indices
    }
}

Answer 3

Here are 2 functions. One returns [Range<String.Index>], the other returns [Range<Int>]. If you don't need the former, you can make it private. I've designed it to mimic the range(of:options:range:locale:) method, so it supports all the same features.

import Foundation

let s = "abc abc  abc   abc    abc"


extension String {
    func allRanges(of aString: String,
                   options: String.CompareOptions = [],
                   range: Range<String.Index>? = nil,
                   locale: Locale? = nil) -> [Range<String.Index>] {

        //the slice within which to search
        let slice = (range == nil) ? self : self[range!]

        var previousEnd: String.Index? = s.startIndex
        var ranges = [Range<String.Index>]()


        while let r = slice.range(of: aString, options: options,
                                  range: previousEnd! ..< s.endIndex,
                                  locale: locale) {
            if previousEnd != self.endIndex { //don't increment past the end
                previousEnd = self.index(after: r.lowerBound)
            }
            ranges.append(r)
        }

        return ranges
    }

    func allRanges(of aString: String,
                   options: String.CompareOptions = [],
                   range: Range<String.Index>? = nil,
                   locale: Locale? = nil) -> [Range<Int>] {
        return allRanges(of: aString, options: options, range: range, locale: locale)
                    .map(indexRangeToIntRange)
    }

    func indexToInt(_ index: String.Index) -> Int {
        return self.distance(from: self.startIndex, to: index)
    }

    func indexRangeToIntRange(_ range: Range<String.Index>) -> Range<Int> {
        return indexToInt(range.lowerBound) ..< indexToInt(range.upperBound)
    }
}

print(s.allRanges(of: "abc") as [Range<String.Index>])
print(s.allRanges(of: "abc") as [Range<Int>])

If you would like just the start indices of each, just tack on .map{ $0.lowerBound }

Answer 4

You just keep advancing the search range until you can't find any more instances of the substring:

extension String {
    func indicesOf(string: String) -> [Int] {
        var indices = [Int]()
        var searchStartIndex = self.startIndex

        while searchStartIndex < self.endIndex,
            let range = self.range(of: string, range: searchStartIndex..<self.endIndex),
            !range.isEmpty
        {
            let index = distance(from: self.startIndex, to: range.lowerBound)
            indices.append(index)
            searchStartIndex = range.upperBound
        }

        return indices
    }
}

let keyword = "a"
let html = "aaaa"
let indicies = html.indicesOf(string: keyword)
print(indicies) // [0, 1, 2, 3]

Answer 5

This could be done with recursive method. I used a numeric string to test it. It returns an optional array of Int, meaning it will be nil if no substring can be found.

extension String {
    func indexes(of string: String, offset: Int = 0) -> [Int]? {
        if let range = self.range(of : string) {
            if !range.isEmpty {
                let index = distance(from : self.startIndex, to : range.lowerBound) + offset
                var result = [index]
                let substr = self.substring(from: range.upperBound)
                if let substrIndexes = substr.indexes(of: string, offset: index + distance(from: range.lowerBound, to: range.upperBound)) {
                    result.append(contentsOf: substrIndexes)
                }
                return result
            }
        }
        return nil
    }
}

let numericString = "01234567890123456789012345678901234567890123456789012345678901234567890123456789"
numericString.indexes(of: "3456")