一个需求引发的算法及优化(KMP算法)

1.需求

先分析下这个需求,这是一个简单的搜索功能,在你输入一段字符后会得到后端返回的搜索结果,很常见.但是问题是需要将你输入的字符串在搜索结果中变色,那就要得到子串在父串中的位置.

其实就是在一个字符串里面匹配另一个字符串,然后如果匹配成功返回在主串中子串的 startIndex.

2.算法分析

说完需求,再来看算法,其实看完这个需求我就想到在 leetCode 上刷过的一道题链接.
以下图来分析:

首先遍历父串,得到与子串中第一个字符相等的 index,然后在遍历子串,比较子串与父串 index 位之后字符是否相等.如果不相等,那么继续遍历父串得到下一个 index, 直到找到子串匹配父串或者没找到退出循环.
这是个简单的思路,就直接贴代码:

/*
 impStr()
 * Time Complexity: O(nm), Space Complexity: O(n)
 */
func impStr(haystack: String, needle: String) -> Int {
    let hChars = Array(haystack.characters)
    let nChars = Array(needle.characters)
    guard hChars.count >= nChars.count else {
        return -1
    }
    guard nChars.count != 0 else {
        return 0
    }
    for i in 0...(hChars.count - nChars.count) {
        // 找到父串中与子串第一个字符相等的 index
        if hChars[i] == nChars[0] {
            for j in 0..<nChars.count {
                // 如果子串某一位和父串不相等,退出循环
                if hChars[i+j] != nChars[j] {
                    break
                }
                // 找到子串匹配父串
                if j + 1 == nChars.count {
                    return i
                }
            }
        }
    }
    return -1
}

小需求搞定,easy!
但是…时间复杂度是O(nm)啊…再优化下?

3.算法优化

再回头看看上面的分析,在子串某一位匹配失败后,父串开始下一次循环,然后之前已经对齐的子串错开,那么父串的匹配必然失败,在上面的算法中没有处理这一块信息,如果有一个很长的子串到最后几位才匹配失败的话,那这个算法的效率就非常低下,毕竟是O(nm)的复杂度.
那有什么办法的?

KMP算法

KMP 算法会利用之前已经匹配成功的部分子串来减少父串的循环次数,当子串匹配失败后,不去让父串继续遍历,而且通过移动子串的 index 来重新开始下一次匹配.

KMP 算法小解

从上图来分析下 KMP 的流程,在第一次子串的最后一位D与父串E不相等,此时父串ABCDAB与子串的ABCDAB是匹配的,此时父串和子串拥有相同的前缀AB,如果父串下次循环的其实位置就是AB时,就是父串的后缀和子串的前缀对齐,那么下一次匹配开始时已经成功匹配了两个字符,然后继续匹配.
不难看出,这个算法充分利用了匹配好的字符串,减少了父串循环的次数,但是问题是需要去计算匹配成功的字符串的是否存在相同的前缀与后缀,怎么计算之后再说,先看子串移动的位数也就是父串循环的 index的起始位置的偏移量的计算.
父串向右偏移的位数 = 匹配成功的字符串长度 - 已匹配成功的字符串的最大公共前缀后缀长度
上图: 父串向右偏移的位数(4) = = 匹配成功的字符串长度(6) - 已匹配成功的字符串的最大公共前缀后缀长度(2)
那就需要另一个算法来计算一个字符串的最大公共前缀后缀长度,贴一下算法:

func getNext(patternStr: String) -> [Int] {
     let count = patternStr.characters.count
     var k = -1
     var next = Array(repeating: -1, count: count)
     for var j in stride(from: 0, to: count - 1, by: 1) {
        while (k != -1 && patternStr[patternStr.index(patternStr.startIndex, offsetBy: j)] != patternStr[patternStr.index(patternStr.startIndex, offsetBy: k)]) {
            k = next[k]
         }
         k += 1
         j += 1
         next[j] = k
      }
      return next
}

这个函数入参就是子串,得到的一个等于子串 length的字符串,每个 index 是除了当前 character 的最大前后缀长度.

字符串匹配

计算完成 next数组之后,接下来就可以用这个数组去在父串中找到子串的出现位置,假设匹配到 i 位置时,父串匹配了子串的第一个character, 接下来就要比较父串的 i+1和子串的1来匹配,直到出现第j 个位置不匹配,那么就将子串中0..

// KMP 算法 字符串匹配
func strStr(_ haystack: String, _ needle: String) -> Int {
    guard haystack.characters.count >= needle.characters.count else {
        return -1
    }
    guard needle.characters.count != 0 else {
        return 0
    }
    guard haystack.contains(needle) else {
        return -1
    }
    var indexI = haystack.startIndex
    var indexJ = needle.startIndex
    var j = 0
    let next = getNext(patternStr: needle)
    while (indexI < haystack.endIndex && indexJ < needle.endIndex) {
        if j == -1 || haystack[indexI] == needle[indexJ] {
            j += 1
            if indexJ == needle.index(before: needle.endIndex) {
                return haystack.distance(from: indexJ, to: indexI)
            }
            indexI = haystack.index(indexI, offsetBy: 1)
            indexJ = needle.index(indexJ, offsetBy: 1)
        } else {
            let distance = haystack.distance(from: needle.startIndex, to: indexJ)
            j = next[distance]
            if j == -1 {
                indexJ = needle.startIndex
            } else {
                indexJ = needle.index(needle.startIndex, offsetBy: j)
            }
        }
    }
    return -1
}

KMP 算法的复杂度是 O(m+n),比之前的O(mn)好多了,基本上这个需求也就可以完美收工了.

4.闲话

其实对客户端来说,算法重要不重要呢?能不能用到呢?
其实我的答案是重要,当你遇到一个类似我遇到的这种需求,不管你用了怎么耗时的算法完成,从 UI 的表现来说可能都一样,但是会觉得不够好,还可以去优化,我觉得这才是能让自己去不断进步的一种想法.

5.参考

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
http://blog.csdn.net/yutianzuijin/article/details/11954939/
https://github.com/cbangchen/SwiftAlgorithms