KMP算法swift版本

func KMP(_ str:String, _ pattenStr: String) -> Int {
    var j = 0
    let nexts = get_nexts(pattenStr)
    let strChars = Array(str)
    let pattenStrChars = Array(pattenStr)
    for i in 0..<str.count {
        while j > 0 && strChars[i] != pattenStrChars[j] {//遇到坏字符，查询nexts数组并改变模式串的起点
            j = nexts[j]
        }
        if strChars[i] == pattenStrChars[j] {
            j += 1
        }
        if j == pattenStr.count {
            return i - pattenStr.count + 1
        }
    }
    return -1
}

func get_nexts(_ pattenStr:String) -> [Int] {
    var nexts:[Int] = [Int](repeating: 0, count: pattenStr.count)
    let pattenChars = Array(pattenStr)
    var j = 0
    for i in 2..<pattenStr.count {
        while j != 0 && pattenChars[j] != pattenChars[i - 1] {//如果当前i-1于j无法匹配则 j = nexts[j]
            j = nexts[j];
        }
        if (pattenChars[j] == pattenChars[i - 1]) {//模板字符串最长可匹配的前缀字符串
            j += 1
        }
        nexts[i] = j//填充next[i]
    }
    return nexts
}

let str = "abcdabg"
let p = "cda"

let position = KMP(str, p)
print("position:\(position)")

nexts分析图

从上图中我们可以分析到，与其说是next数组，不如说是最小公共子前缀数组
那么问题来了，怎么求这个next数组呢？
根据我们前面分析的next数组的定义，可以找到下面的规律：
如果新加入的字符与前一个最长公共前缀子串的后一个字符相同：

next[i]与next[i-1]的关系
这里的深绿色部分长度是可以为0的，对后面计算没有影响。
next[i-1]与next[i]
在这种情况下，原来的深绿色部分就不能用了，显然，我们要缩小深绿色的部分，还要满足最长公共前缀子串的要求，也就像下面这个样子：
j = next[i]

这个蓝色的部分怎么求呢？这就是很多博客和代码里面没有说清楚的，最让人头痛的回退操作，就是那个臭名昭著的”j= next[j]“。
我们换一种理解方式，这个蓝色的部分，首先要内容相同，其次还要位于深绿色部分的开头和结尾，这不就是深绿色部分的最长公共前缀子串吗？

j=next[i]

也就是这样

j=next[i]

更新j = next[j]后，又回到这个问题的起点了，然后再次判断s[i-1]和s[j]是否相同就可以了。
至此，我们终于搞懂那个让人费解的回退操作到底是什么意思了，其实就是在当前的公共前缀已经不能用了，那就继续去尝试这个公共前缀的公共前缀，一直试到成功或者公共前缀的长度为0时为止。

参考文章
https://blog.csdn.net/Leycaner/article/details/108301195