1.需求

搜索3.jpg

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

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

2.算法分析

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

1.png

/*
 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 算法小解

2.png

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..<j的字符串去从 next 数组中找到最长公共前后缀长度.接下来就讲父串的 i偏移 next 数组中得到的 index,然后继续匹配.

   /*
     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