Swift-从字符串匹配看普通算法与KMP算法

最近在leetcode上刷题，当然，是用swift，中间的辛酸经历就不提了，不得不说swift在便利性上的确十分强大，但其效率也的确相较C++、JAVA等显得相对低下，在这里不得不吐槽leetcode的Time Limit Exceeded魔咒似乎并不随着语言环境的不同而有所改变，每当看着Top solutions上一些C++、JAVA信徒用同样的算法打败了Time Limit Exceeded魔咒而我却一次又一次在魔咒面前止步不得不说我感到我的心在滴血。

然而就是又一次在刷题苦于ime Limit Exceeded魔咒时看到了KMP算法，当即被晦涩难懂的理论砸的懵逼了，在好半天的理解加题目应用才逐渐明白过来。

KMP算法的原理可以看这篇，在这么多篇的博文中这篇算是我看过最浅显易懂的了。

我只是将KMP算法的原理通过实际题目以自我的理解剖析一遍。

---

算法题是这样的：
Repeated Substring Pattern

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"
Output: True

Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"
Output: False

Example 3:

Input: "abcabcabcabc"
Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

简单明了的算法题，给你一个不为空的字符串，你需要通过算法得出这个字符串中是否有字符成循环关系，返回布尔值。

简单的审题我们可以写成这样的伪代码。

//for循环套for循环。
//外层的循环从字符串的0下标开始截取每一个字符组成字符串。
//内层的循环从外层字符串的长度+1开始循环，截取之后的每个字符组成字符串并与外层的可变字符进行比较
//定义一个变量，当内层字符串与外层字符串相同时+=1，若变量在跳出内层循环时的值与原始字符串的长度 / 外层字符串的长度 - 1（外层字符串的长度） 的值相等则输出True，否则输出False。

通过伪代码你即可看出这是多繁复的写法了，当然我们可以通过加上一些条件进行筛选而减少步骤，例如

//若外层字符串与内层字符串长度不相等则不进行比较
//若外层字符串长度 % 原始字符串长度不为0则不进行内部循环

等等。
这些筛选条件的确让内部操作减少但也让代码变得更加繁琐，而且就算这样也没抵挡地住Time Limit Exceeded魔咒。

那么，换一种思考法，我们通过截取字符串并让它循环增殖再与原字符串比较，如此，是否更高效？

func repeatedSubstringPattern(_ str: String) -> Bool {
    for i in (1...str.characters.count/2).reversed(){
        if str.characters.count % i == 0 {
            let s = str.substring(to: str.index(str.startIndex, offsetBy: i))
            var s2 = ""
            let m = str.characters.count / s.characters.count
            for _ in 0..<m{
                s2.append(s)
            }
            if s2 == str { return true }
        }
    }
    return false
}

这种方法比起第一种拥有更简洁的代码，并且，其效率相较于第一种也显得高上一节（你看外部for循环都砍一半了，内部for循环更是只有m次）。
不得不说Swift的某些字符串操作手法简直是天怒人怨，截取字符串要写成这样

            let s = str.substring(to: str.index(str.startIndex, offsetBy: i))

如果要获得某一个具体位置的字符更是要如此

        let sc = str.characters[str.characters.index(str.characters.startIndex, offsetBy: i)]

不要说 for c in s.characters，两个字符串比较时还是要加个变量记录位置ORZ

然而，终究还是抵挡不住魔咒，虽然第二种方法效率高上一截，但依然抵挡不住魔咒，（顺便一提同样的代码我写了份C++的直接通过了……）
于是在Top solutions我找到了KMP算法

func repeatedSubstringPattern1(_ str: String) -> Bool {
    //KMP算法
    let length = str.characters.count
    //i表示的是下一需要比较的字符串的下标
    var i = 1,j = 0
    var next = [Int](repeating:0, count:length+1)
    while i < length {
        if str.characters[str.characters.index(str.characters.startIndex, offsetBy: i)] == str.characters[str.characters.index(str.characters.startIndex, offsetBy: j)] {
            //若位置i的字符与j匹配的上则对下一个位置的字符进行比较
            //同时，对next数组（即最大公共长度数组进行更新），其下标中的数值即是当前的最大公共长度，即j+=1后的值
            i+=1
            j+=1
            next[i] = j
        } else if j == 0 {
            //若公共长度为一，这种情况可能出现在一开始，也就是字符一开始没有匹配上的时候，亦可能出现在匹配过程中因为匹配不上而不断切割公共长度，直到公共长度为0时。
            //此时，将需要比对的字符向后移动一位进行匹配，也就是i+=1
            i+=1
        } else {
            //当字符不匹配而公共长度又不为0时则不断切割最大公共长度，即前移j在字符串中的位置，也就是将之前保存的next容器中的最大公共长度进行切割，获取j的历史值
            j = next[j]
        }
    }
    return  next[length] > 0 && next[length] % (length - next[length]) == 0
}

哈哈哈哈！龟儿子，就这样也想难倒我！

……