(一)前言

所謂的字符串匹配就是在一個長字符串(可稱文本T)中找一個短字符串(可稱模式P)，看長字符串中是否存在短字符串，若存在則返回出現(xiàn)的第一個位置，若不存在則返回一個標(biāo)記。字符串搜索算法有很多，比較知名的自然是大名鼎鼎Knuth-Morris-Pratt 算法(簡稱 KMP)和Boyer-Moore(簡稱BM)。關(guān)于這兩個算法的實現(xiàn)比較復(fù)雜，需要很多的前置知識，不在這里長篇大論，有興趣的同學(xué)，可自行搜索。

今天給大家介紹一個相對高效且簡單的Horsepool算法，Horsepool算法是Boyer-Moore算法的簡化版本，為了方便理解Horsepool算法，我們先從樸素字符串匹配算法談起。

(二)樸素(暴力)字符串匹配算法

先看樸素的字符串匹配算法的過程：

算法規(guī)則：用i，j表示兩字符串正在比較的字符位置。若長字符串與短字符串該位置字符匹配，則繼續(xù)比較二者后面的字符，即i加1，j加1。不匹配，分別回溯i，j。這個算法非常樸素，通常性能極差。最壞情況舉例：aaaaaaaab和aaab匹配，需要重復(fù)比較字符多次。

樸素搜索Python實現(xiàn)：

# txt 長字符串，pat 短字符串def forceSearch(txt, pat): M = len(txt) N = len(pat) for i in range(M-N+1): for j in range(N): if txt[i+j]!=pat[j]: break else: return i return

(三)Horspool算法

Horspool算法把短字符串(以下簡稱模式P)與長字符串(以下簡稱文本T)的開頭字符對齊，從模式P的最后一個字符開始比較，如果嘗試比較失敗了，它把模式P向后移。每次嘗試過程中比較是從右到左的。

假設(shè)對齊后文本T中最后一個對齊字符為X(代表任意字符)，Horspool算法根據(jù)X的不同情況來確定移動距離(樸素算法每次不匹配只右移一位)，無論X是否和模式的最后一個字符相匹配，一般來說，會存在下面四種情況：

情況1，如上圖所示，對齊后，文本T中最后一個字符對齊X為o，與模式P最后一個字符g不匹配，且模式P中不存在X(也就是字母o)，模式P的移動長度就是它的全部長度，移到所示的位置。

情況2，如上圖所示，對齊后，文本T的最后一個對齊字符X為e，恰好和模式P最后一個字符匹配。但是從右向左比較時，有字符不匹配，比如此時的o和a不匹配。由于模式P中只包含一個字符X(也就是e)，模式P的移動長度就是它的全部長度，移到所示的位置。

情況3，如上圖所示，對齊后，文本T的最后一個對齊字符X為a，與模式P最后一個字符g不匹配。移動時應(yīng)該把模式P中最右邊的X(a)和文本中的X(a)對齊。

情況4，如上圖所示，對齊后，文本T的最后一個對齊字符X為a，與模式P最后一個字符a匹配，但是從右向左比較時，有字符不匹配，比如此時的n和i不匹配。移動時，應(yīng)把模式P除X(a)外，最右邊字符X(a)和文本T中的X(a)對齊。

綜上所述，比起樸素算法每次總是移動一個位置，從右到左的字符比較使模式不匹配時可以移動得更遠(yuǎn)。然而，如果在每次嘗試時都必須檢查模式P中的每個字符來確定移動距離，它的優(yōu)勢也會喪失殆盡。我們可以預(yù)先算出遇到某個字符要移動的距離，并把它存在一個表中。

示例如下，對于模式BARBER，移動距離如下表所示：

這里對字符A，B做一下解釋，方便還沒有理解的同學(xué)，加深理解。

若對齊后，文本T的最后一個對齊字符X為A，A與R不匹配，BARBER，A與結(jié)尾處R字符距離為4。

若對齊后，文本T中最后一個對齊字符X為B，B與R不匹配，BARBER，最右邊B與結(jié)尾處R字符距離為2。

若對齊后，文本T中最后一個對齊字符X不在模式P中，則移動距離為模式P長度6。

Horspool算法Python實現(xiàn)：

def horspool(txt,pat): n = len(txt) m = len(pat) table = [m]*96 #ascii中可打印字符有96，且前32為控制字符 for i in range(m - 1): table[ord(pat[i]) - 32 ] = m -1 - i #從左至右掃描模式，相同字符的最后一次改寫恰好是該字符在模式串的最右邊 i = m - 1 while i <= n - 1: k = 0 while k <= m-1 and pat[m - 1 - k] == txt[i - k]: k += 1 #向左比較下一個字符 if k == m: return i - m + 1 #匹配成功返回索引 else: i += table[ord(txt[i]) - 32] #根據(jù)表格移動模式串 return -1

(四)參考文獻(xiàn)

[1]https://blog.csdn.net/khwkhwkhw/article/details/51288502

[2]https://www.runoob.com/python/python-for-loop.html

[3]https://www.asklib.com/view/fbef10420ab8.html

[4]https://blog.csdn.net/gilzhy/article/details/16803993

[5]https://ethsonliu.com/2018/04/kmp.html

總結(jié)

以上是生活随笔為你收集整理的# 字符串从右往左查找_字符串匹配（搜索，查找）算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。