swift 查找给定子字符串的所有位置 朴素字符串匹配、KMP字

思路：
使用朴素字符串搜索，依次扫描整个字符串

/// 查找所有的子字符串所在位置
/// - Parameter string: 给定的模式P
func findAllIndex(_ string:String) -> [NSRange]{
    var ranges:[NSRange] = []
    if string.elementsEqual(""){
        return ranges
    }
    let zero = self.startIndex
    let target = Array(string)
    let total = Array(self)
    
    let lenght = string.count
    var startPoint = 0
    
    while total.count >= startPoint + string.count{
        if total[startPoint] == target[0]{
            let startIndex = self.index(zero, offsetBy: startPoint)
            let endIndex = self.index(startIndex, offsetBy: lenght)
            let child = self[startIndex..<endIndex]
            if child.elementsEqual(string){
                ranges.append(NSRange.init(location: startPoint, length: lenght))
                startPoint += lenght
            }else{
                startPoint += 1
            }
        }else{
            startPoint += 1
        }
    }
    
    return ranges
}

使用KMP算法实现：

/// KMP字符串查询
/// - Parameter p: 查询的模式
func kmpFindAllIndex(_ p:String) -> [NSRange]{
    var ranges:[NSRange] = []
    let n = self.count
    let m = p.count
    let π = computePrefix(p)
    var q = 0
    
    for i in 0..<n{
        while q > 0 && !p.getCharacter(q).elementsEqual(self.getCharacter(i)){
            q = π[q]
        }
        
        if p.getCharacter(q).elementsEqual(self.getCharacter(i)){
            q += 1
        }
        
        if q == m{
            ranges.append(NSRange.init(location: i, length: m))
            q = π[q]
        }
    }
    return ranges
}


/// 计算KMP对应的前缀函数π数组
/// - Parameter p: 模式P
func computePrefix(_ p:String) -> [Int]{
    let m = p.count
    var π:[Int] = [Int](repeatElement(0, count: m + 1))
    π[0] = 0
    var k = 0
    for q in 1..<m{
        while k > 0 && !p.getCharacter(k).elementsEqual(p.getCharacter(q)){
            k = π[k]
        }
        if p.getCharacter(k).elementsEqual(p.getCharacter(q)){
            k += 1
        }
        π[q] = k
    }
    
    return π
}


/// 获取单个字符
/// - Parameter index: <#index description#>
func getCharacter(_ index:Int) -> String{
    return getChildsString(index, 1)
}

/// 获取特定位置，长度 字符串
/// - Parameters:
///   - start: 开始位置
///   - length: 长度
func getChildsString(_ start:Int,_ length:Int) -> String{
    let startIndex = self.index(self.startIndex, offsetBy: start)
    let endIndex = self.index(startIndex, offsetBy: length)
    return String(self[startIndex..<endIndex])
}