字符串匹配算法

Sunday 算法

从前往后匹配，匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符

1. 如果该字符串没有在模式串中出现过，则直接跳过，移动位数 = 模式串长度 + 1

2. 否则，移动位数 = 模式串中该字符从右往左数的位置（1 为初始索引）

   
   动图

举例

主串”substring searching”中查找模式串”search”

1. 主串和模式串对齐
2. 在第2个字符串处不匹配
3. 当前匹配串最末位的下一位字符 "i 不在模式串中
4. 直接将匹配位置移动到 n 的位置
5. 仍然不匹配，但是此时匹配串最末位的下一个字符 "r" 在模式串中，移动模式串，使两个 "r" 对齐。
6. 匹配成功

LeetCode 28 题

28 实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

func strStr(_ haystack: String, _ needle: String) -> Int {
    guard !needle.isEmpty else {
        return 0
    }
    guard !haystack.isEmpty else {
        return -1
    }
    let needle = Array(needle)
    let hayStack = Array(haystack)

    // pattern offset
    var patternDic: [Character: Int] = [:]
    for index in 0..<needle.count {
        patternDic[needle[index]] = needle.count - index
    }

    var index: Int = 0
    while index <= (hayStack.count - needle.count) {
        var j: Int = 0
        // 判断 need 与 index...(index + j) 是否匹配
        while hayStack[index + j] == needle[j] {
            j += 1
            if j >= needle.count {
                return index
            }
        }
        // 不匹配，则计算偏移
        guard index + needle.count < hayStack.count else {
            return -1
        }
        let offset = patternDic.keys.contains(hayStack[index + needle.count]) ?
                                              patternDic[hayStack[index + needle.count]]! :
                                              needle.count + 1
        index += offset
    }
    return -1
}

Sunday 算法缺点

主串：aaaabaaaabaaaabaaaa
模式串：aaaaa
匹配失败，模式串每次移动位置 1，时间复杂度为 O(m*n)

参考

1. 动画演示Sunday字符串匹配算法——比KMP算法快七倍！极易理解！
2. 字符串匹配算法之Sunday算法