字符串匹配
1.樸素的串匹配算法(暴力解法)
1.1 分析
設(shè)t是目標(biāo)串（母串）觅捆，p是模式串（待匹配串）先舷，i , j 分別指向 模式串 和 目標(biāo)串，m途乃、n分別是模式串p和目標(biāo)串t的長(zhǎng)度俩功。
- 從目標(biāo)串的第0個(gè)字符幻枉，挨個(gè)進(jìn)行比較，遇到不相等的字符就停止诡蜓。
- 模式串與目標(biāo)串的下一個(gè)字符進(jìn)行比較熬甫，重復(fù)上一個(gè)步驟。
- 一個(gè)一個(gè)字符遍歷目標(biāo)串直到找到為止万牺。
1.2 Python實(shí)現(xiàn)：
def match(t:str, p:str):
'''
t:目標(biāo)串(母串)
p:模式串(要匹配的字符串)
返回與模式串在目標(biāo)串中第一次出現(xiàn)時(shí)的下標(biāo)
''' m, n = len(p), len(t) # m 和 n分別是字符串 p 和 t的長(zhǎng)度
i, j = 0, 0
while i < m and j < n:
if p[i] == t[j]:
i, j = i+1, j+1
else:
i, j = 0, j-i+1 # j-i得到當(dāng)前j的下標(biāo)罗珍，+1指向目標(biāo)串的下一個(gè)元素
if i == m:
return j-i # 返回此時(shí)母串中j的下標(biāo)
return -1
res = match("ababcabcacbab", "abcac")
print(res)
程序運(yùn)行結(jié)果是5；
1.3 時(shí)間復(fù)雜度分析
暴力匹配最壞的情況下脚粟，每一次都進(jìn)行比較覆旱，最后一趟才匹配上，共n-m+1趟核无，每次模式串都進(jìn)行了匹配為m次扣唱，故這個(gè)算法的時(shí)間復(fù)雜度為：O(m x n)。
樸素算法（暴力匹配）的缺點(diǎn)：
- 把每次字符都看做完全獨(dú)立的操作，沒(méi)有利用字符串本身的特點(diǎn)噪沙，字符串只有有窮多個(gè)字符炼彪。
- 沒(méi)有利用前面已經(jīng)比較的字符串得到的信息。
匹配字符串的特點(diǎn)：
- 模式串不太長(zhǎng)
- 目標(biāo)串的每一個(gè)字符來(lái)源于一個(gè)又窮集合正歼，不是無(wú)窮多種取值
- 每個(gè)串有固定的長(zhǎng)度
2.無(wú)回溯串匹配算法(KMP算法)
KMP算法是由3個(gè)外國(guó)人最先發(fā)現(xiàn)的辐马，并以他們的名字首字母命名，該算法是一個(gè)高效的串匹配算法局义，該算法比較難理解喜爷，但是時(shí)間復(fù)雜度大大降低。該算法主要優(yōu)化了樸素算法里把模式串里的字符看做單獨(dú)隨機(jī)字符的做法萄唇。具體如下：
- 每一次比較之后檩帐，找到不同的元素
- 然后通過(guò)next數(shù)組找到模式串下一次匹配的字符下標(biāo)
- 構(gòu)造next數(shù)組
2.1 KMP算法主函數(shù)
例：使用KMP算法把下圖中的模式串在目標(biāo)串進(jìn)行進(jìn)行查找，返回第一次出現(xiàn)時(shí)的下標(biāo)：
def match_KMP(t, p, gen_pnext):
""":arg
t : 目標(biāo)串
p : 模式串
next : 模式串的next數(shù)組
""" i, j = 0, 0
n, m = len(t), len(p) # m 另萤、 n 分別是模式串 和 目標(biāo)串的長(zhǎng)度
while i < m and j < n:
if i == -1 or t[j] == p[i]:
i, j = i+1, j+1
else:
i = gen_pnext[i]
if i == m: # 找到匹配的子字符串湃密，返回其下標(biāo)
return j-i
return -1
2.2 next數(shù)組
首先我們介紹一下前綴和后綴的概念：
給出一個(gè)字符串 abcacab 該字符串相等的最長(zhǎng)的前綴和后綴是ab。
練習(xí)：
1.求字符串 abbcabb四敞，該字符串相等的前后綴為abb泛源。
2.求字符串acgcca ,該字符串相等的前后綴為 a。
通過(guò)找到相等的前后綴目养，我們主要用來(lái)在KMP匹配一次之后俩由，目標(biāo)串和模式串遇到不同的字符時(shí)毒嫡，在該位置目標(biāo)串下次匹配的模式串字符的位置癌蚁。如上圖所示：目標(biāo)串的a字符和模式串的c字符不一致，這時(shí)候需要構(gòu)造next數(shù)組找到下次模式串匹配的字符位置a,這里的計(jì)算方法是：在模式串的不同字符的前的子字符串里找到相等的最大的前后綴的下一個(gè)字符的下標(biāo)作為下次模式串匹配的位置兜畸。這里 ab 字符努释，沒(méi)有相等的前后綴，返回下標(biāo)0,對(duì)應(yīng)的字符是a咬摇。
第二次匹配時(shí)：遇到目標(biāo)串里的字符 b 和 模式串里的 c 不一致伐蒂，我們找 子字符串：abca 里 最長(zhǎng)相等前后綴 為 a，則取下標(biāo)1對(duì)應(yīng)的 b 字符與第一次匹配失敗時(shí)的 目標(biāo)串的 'b' 字符進(jìn)行匹配肛鹏。
def gen_pnext(p):
i, k, m = 0, -1, len(p)
pnext = [-1] * m
while i < m-1:
if p[i] == p[k] or k == -1:
i, k = i+1, k+1
pnext[i] = k
else:
k = pnext[k]
return pnext
這里的 gen_pnext() 函數(shù)就是我們上面解釋的生成 next 數(shù)組的函數(shù)逸邦。下面稍微容易理解一點(diǎn)。
def p_next(patttern:str):
""":arg
pattern:傳入的是待匹配字符串
""" i, k = 0, -1 # i 指向 pattern 字符串在扰， k 初值為 -1 pnext = [-1] * len(patttern) # 生成一個(gè)長(zhǎng)度和 pattern 一致的數(shù)組缕减，初始值都為-1
while i < len(patttern)-1:
if k == -1:
i, k = i + 1, k + 1
pnext[i] = k
elif patttern[k] == patttern[i]:
i, k = i + 1, k + 1
pnext[i] = k
else:
k = pnext[k] # 不相等 k 的值就會(huì)一直指向 pnext[k] return pnext
上面的求next的函數(shù)很不好理解，可以結(jié)合圖片理解芒珠。
2.3 時(shí)間復(fù)雜度
一次KMP算法的完整執(zhí)行包括構(gòu)造 pnext 表 和 實(shí)際匹配桥狡，設(shè)模式串和目標(biāo)串長(zhǎng)度分別為 m 和 n， KMP算法的時(shí)間復(fù)雜度是 O(m+n)。多數(shù)情況下 m<<n,可以認(rèn)為這個(gè)算法的時(shí)間復(fù)雜度是 O(n)裹芝。
碼字不易部逮，感覺(jué)對(duì)你有幫助可以加個(gè)關(guān)注哈。
