KMP

KMP.swift

public extension String {
    func find(_ text: String) -> [Int] {
        guard text.count <= self.count else {// 要查找的子串长度大于字符串长度，比较没有了意义……
            return []
        }
        // 字符串子串前缀与后缀最大公共长度
        let getNext: (String) -> [Int] = { txt -> [Int] in
            var arr = [Int](repeating: 0, count: txt.count+1)
            //0和1的值肯定是0
            arr[0] = 0
            arr[1] = 0
            //根据arr[i]推算arr[i+1]
            for i in 1..<txt.count {
                var j = arr[i]
                // 比较i位置与j位置的字符
                // 如果不相等，则j取arr[j]
                while j > 0, txt[i] != txt[j] {
                    j = arr[j]
                }
                // 如果相等，则j加一即可
                if txt[i] == txt[j] {
                    j += 1
                }
                arr[i+1] = j
            }
            return arr
        }
        var next = getNext(text)
        var index = [Int]()
        // i表示text中的位置，j表示查找字符串的位置
        var j = 0
        for i in 0..<self.count {// 遍历字符
            // 这里是KMP算法的关键，位置移动为next[j]
            while j > 0, self[i] != text[j] {
                j = next[j]
            }
            // 如果i位置和j位置字符相同，移动一位
            if self[i] == text[j] {
                j += 1
            }
            // 如果j已经找到了find的尾部目标是已经找到
            if j == text.count {
                // i-j+1即为目标字符串在text中出现的位置
                index.append(i-j+1)
                // 这里是KMP算法的关键，位置移动为next[j]
                j = next[j]
            }
        }
        return index
    }

    subscript (i: Int) -> Character {
        return self[index(startIndex, offsetBy: i)]
    }
}