算法练习：字符串匹配算法

[ShannonChenCHN]

大纲

• BF 算法
• RK 算法
• BM 算法
• KMP 算法
• Trie 树
• AC 自动机

题目列表

• KMP
  • 28. 实现 strStr()

[ShannonChenCHN]

理论知识

参考：

• https://time.geekbang.org/column/article/71187?code=qCVA2cDQgRT3zHOy%2FZk21JRtNkN7CjYC31L8M0omrqQ

[ShannonChenCHN]

28. 实现 strStr()

2021.05.08 08:30 am ~ 09:00 am
2021.05.09 10:00 am ~ 11:00 am

参考题解：

• https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
• https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/

延伸阅读：https://stackoverflow.com/questions/28663749/why-is-my-swift-loop-failing-with-error-cant-form-range-with-end-start

解法一：暴力解法（双指针逐个比较）

思路：两个指针 i 和 j 分别指向 haystack 和 needle，遍历 haystack，每次以第 i 个字母作为首字母，跟 needle 逐个字母进行比较。

边界条件：需要考虑 haystack 和 needle长度为 0 以及两者长度相同的情况。

时间复杂度：O(m x n)
空间复杂度：O(1)

使用 while 语句：

class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        let m = haystack.count
        let n = needle.count
        guard n > 0 else {
            return 0
        }

        let haystackList = Array(haystack)
        let needleList = Array(needle)

        var i = 0
        while i <= (m-n) {
            // 从第 i 个开始逐字比较
            var j = 0
            while j < n {
                if haystackList[i+j] != needleList[j] { // 逐个字母比较
                    break
                }
                if j == n - 1 { // 最后一个字母都匹配成功了，说明完全匹配
                    return i
                }
                j += 1
            }
            
            i += 1
        }

        return -1
    }
}

使用 for 循环：

class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        let m = haystack.count
        let n = needle.count
        guard n > 0 else {
            return 0
        }

        let haystackList = Array(haystack)
        let needleList = Array(needle)

        for i in stride(from: 0, through: m-n, by: 1) {  // 注意：这里不能用 for i in 0...m-n 的形式
            // 从第 i 个开始逐个比较
            for j in stride(from: 0, to: n, by: 1) {
                if haystackList[i+j] != needleList[j] { // 逐个字母比较
                    break
                }
                if j == n - 1 { // 最后一个字母都匹配成功了，说明完全匹配
                    return i
                }
            }
        }

        return -1
    }
}

解法二：KMP 算法

TODO