1.需求

搜索3.jpg

先分析下這個(gè)需求,這是一個(gè)簡(jiǎn)單的搜索功能,在你輸入一段字符后會(huì)得到后端返回的搜索結(jié)果,很常見.但是問題是需要將你輸入的字符串在搜索結(jié)果中變色,那就要得到子串在父串中的位置.

其實(shí)就是在一個(gè)字符串里面匹配另一個(gè)字符串,然后如果匹配成功返回在主串中子串的 startIndex.

2.算法分析

說完需求,再來看算法,其實(shí)看完這個(gè)需求我就想到在 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) {
        // 找到父串中與子串第一個(gè)字符相等的 index
        if hChars[i] == nChars[0] {
            for j in 0..<nChars.count {
                // 如果子串某一位和父串不相等,退出循環(huán)
                if hChars[i+j] != nChars[j] {
                    break
                }
                // 找到子串匹配父串
                if j + 1 == nChars.count {
                    return i
                }
            }
        }
    }
    return -1
}

小需求搞定,easy!
但是...時(shí)間復(fù)雜度是O(nm)啊...再優(yōu)化下?

3.算法優(yōu)化

再回頭看看上面的分析,在子串某一位匹配失敗后,父串開始下一次循環(huán),然后之前已經(jīng)對(duì)齊的子串錯(cuò)開,那么父串的匹配必然失敗,在上面的算法中沒有處理這一塊信息,如果有一個(gè)很長(zhǎng)的子串到最后幾位才匹配失敗的話,那這個(gè)算法的效率就非常低下,畢竟是O(nm)的復(fù)雜度.
那有什么辦法的?

KMP算法

KMP 算法會(huì)利用之前已經(jīng)匹配成功的部分子串來減少父串的循環(huán)次數(shù),當(dāng)子串匹配失敗后,不去讓父串繼續(xù)遍歷,而且通過移動(dòng)子串的 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
}

這個(gè)函數(shù)入?yún)⒕褪亲哟?得到的一個(gè)等于子串 length的字符串,每個(gè) index 是除了當(dāng)前 character 的最大前后綴長(zhǎng)度.

字符串匹配

計(jì)算完成 next數(shù)組之后,接下來就可以用這個(gè)數(shù)組去在父串中找到子串的出現(xiàn)位置,假設(shè)匹配到 i 位置時(shí),父串匹配了子串的第一個(gè)character, 接下來就要比較父串的 i+1和子串的1來匹配,直到出現(xiàn)第j 個(gè)位置不匹配,那么就將子串中0..<j的字符串去從 next 數(shù)組中找到最長(zhǎng)公共前后綴長(zhǎng)度.接下來就講父串的 i偏移 next 數(shù)組中得到的 index,然后繼續(xù)匹配.

   /*
     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 算法的復(fù)雜度是 O(m+n),比之前的O(mn)好多了,基本上這個(gè)需求也就可以完美收工了.

4.閑話

其實(shí)對(duì)客戶端來說,算法重要不重要呢?能不能用到呢?
其實(shí)我的答案是重要,當(dāng)你遇到一個(gè)類似我遇到的這種需求,不管你用了怎么耗時(shí)的算法完成,從 UI 的表現(xiàn)來說可能都一樣,但是會(huì)覺得不夠好,還可以去優(yōu)化,我覺得這才是能讓自己去不斷進(jìn)步的一種想法.

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