暴力匹配算法(Brute Force)

? ? 主串中檢查起始位置分別是0、1、2...n-m且?度為m的n-m+1個(gè)子串，查找跟模式串相匹配

????此算法字符串匹配方式比較簡(jiǎn)單、好懂、暴力，但相應(yīng)的性能不高，也叫樸素匹配算法

? ? 名詞解釋

? ??????我們?cè)谧址瓵中查找字符串B，那字符串A就是主串，字符串B就是模式串。

????????我們把主串的?度記作n，模式串的?度記作m。因?yàn)槭窃谥鞔胁檎夷Ｊ酱?，所以n>m

暴力匹配算法匹配分解圖

? ??在極端情況下，如主串為“aaaaa...aaaaaa”，模式串是“aaaaab”。

????我們每次都比對(duì)m個(gè)字符，要比對(duì)n-m+1次，所以這種算法的最壞情況時(shí)間復(fù)雜度是O(n*m)

? ? 實(shí)際開(kāi)發(fā)絕中大部分情況下常用的算法，原因如下:

? ? ? ? 1.實(shí)際的軟件開(kāi)發(fā)中，大部分情況下，模式串和主串的?度都不會(huì)太?

? ? ? ? ? ? 且每次模式串與主串中的子串匹配時(shí)，當(dāng)不能匹配時(shí)就停止不需要把剩下字符都比對(duì)完

? ? ? ? 2.樸素字符串匹配算法思想簡(jiǎn)單，代碼實(shí)現(xiàn)也非常簡(jiǎn)單。遵循KISS原則

Rabin-Karp算法

????暴力匹配算法BF升級(jí)版

? ? 通過(guò)哈希算法對(duì)主串中n-m+1個(gè)子串分別求哈希值，然后逐個(gè)與模式串的哈希值比較大小。

? ? 若某子串的哈希值與模式串相等，則說(shuō)明對(duì)應(yīng)的子串和模式串相匹配(暫不考慮哈希沖突)。

????因?yàn)楣Ｖ凳菙?shù)字，數(shù)字比較是否相等是非常高效，所以模式串和子串比較的效率就提高

RK算法匹配示意圖

? ??通過(guò)哈希算法計(jì)算子串的哈希值時(shí)需要遍歷子串中每個(gè)字符。

????盡管模式串與子串比較的效率提高了，但算法整體的效率并沒(méi)有提高

? ? 優(yōu)化方案:? ?重點(diǎn)在于哈希算法設(shè)計(jì)

? ? ? ? 主串包含字符個(gè)數(shù)K，把子串先轉(zhuǎn)為K進(jìn)制數(shù)，再轉(zhuǎn)十進(jìn)制作為哈希值

哈希算法設(shè)計(jì)示意圖

? ? ? ? 主串中相鄰兩個(gè)子串的哈希值的計(jì)算公式有一定關(guān)系

相鄰子串哈希值計(jì)算公式示意圖

????????相鄰兩個(gè)子串s[i-1]和s[i]，對(duì)應(yīng)的哈希值計(jì)算公式有交集，具體如下圖:?

????????(子串在主串中的起始位置i，子串?度m)

公式推導(dǎo)示意圖

????????提前計(jì)算26次方值且存儲(chǔ)在?度為m數(shù)組中，“次方”對(duì)應(yīng)數(shù)組下標(biāo)，使用時(shí)根據(jù)下標(biāo)訪問(wèn)

數(shù)組中數(shù)據(jù)分布

? ? 時(shí)間復(fù)雜度

? ??????整個(gè)RK算法包含兩部分，計(jì)算子串哈希值和模式串哈希值與子串哈希值之間的比較

? ? ? ? 第一部分，通過(guò)特殊哈希算法，掃描一遍主串計(jì)算所有子串哈希值，時(shí)間復(fù)雜度為O(n)

? ? ? ? 第二部分，模式串哈希值與單個(gè)子串哈希值比較時(shí)間復(fù)雜度為O(1)，總時(shí)間復(fù)雜度為O(n)

? ? ? ? 整個(gè)RK算法時(shí)間復(fù)雜度為O(n)

? ? 哈希沖突

? ? ? ? 如果哈希算法設(shè)計(jì)存在哈希沖突，沖突時(shí)再對(duì)比下模式串和子串本身

? ??????哈希算法沖突概率要控制，如果存在大量沖突，導(dǎo)致RK算法時(shí)間復(fù)雜度退化