字符串匹配存在的問題

Python中在一個長字符串中查找子串是否存在可以用兩種方法：一是str的find()函數，find()函數只返回子串匹配到的起始位置，若沒有，則返回-1；二是re模塊的findall函數，可以返回所有匹配到的子串。

但是如果用findall函數時需要注意字符串中存在的特殊字符

蠻力法字符串匹配：

將模式對準文本的前m（模式長度）個字符，然后從左到右匹配每一對對應的字符，直到全部匹配或遇到一個不匹配的字符。后一種情況下，模式向右移一位。

代碼如下：

def string_match(string, sub_str): # 蠻力法字符串匹配 for i in range(len(string)-len(sub_str)

1): index = i #

index指向下一個待比較的字符 for j in

range(len(sub_str)): if string[index] ==

sub_str[j]: index =

1

else: break

if index-i ==

len(sub_str): return

i return -1

if __name__ == "__main__": print(string_match("adbcbdc", "dc"))

最壞情況下，該算法屬于Θ(nm)，事實上，該算法的平均效率比最差效率好得多。事實上在查找隨機文本的時候，其屬于線性的效率Θ(n)。

Horspool算法：

Horsepool算法是Boyer-Moore算法的簡化版本，這也是一個空間換時間的典型例子。算法把模式P和文本T的開頭字符對齊，從模式的最后一個字符開始比較，如果嘗試比較失敗了，它把模式向后移。每次嘗試過程中比較是從右到左的。

在蠻力算法中，模式的每一次移動都是一個字符，Horspool算法的核心思想是利用空間來換取時間，提升模式匹配窗口的移動幅度。與蠻力算法不同的是，其模式的匹配是從右到左的，通過預先算出每次移動的距離并存于表中。

代碼如下： __author__ = 'Wang'

from collections import defaultdict def shift_table(pattern): # 生成 Horspool 算法的移動表 # 當前檢測字符為c，模式長度為m #

如果當前c不包含在模式的前m-1個字符中，移動模式的長度m #

其他情況下移動最右邊的的c到模式最后一個字符的距離 table = defaultdict(lambda:

len(pattern)) for index in range(0,

len(pattern)-1): table[pattern[index]] = len(pattern) - 1 -

index return table def horspool_match(pattern, text): # 實現 horspool 字符串匹配算法 # 匹配成功，返回模式在text中的開始部分；否則返回

-1 table =

shift_table(pattern) index = len(pattern) - 1

while index <= len(text) -

1: print("start matching at",

index) match_count = 0

while match_count < len(pattern)

and pattern[len(pattern)-1-match_count] ==

text[index-match_count]: match_count = 1

if match_count ==

len(pattern): return index-match_count

1

else: index =

table[text[index]] return -1

if __name__ == "__main__": print(horspool_match("barber",

"jim_saw_me_in_a_barbershopp"))

顯然，Horspool算法的最差效率屬于屬于Θ(nm)。在查找隨機文本的時候，其屬于線性的效率Θ(n)。雖然效率類型相同，但平均來說，Horspool算法比蠻力算法快很多。

總結

以上是生活随笔為你收集整理的文本字符分析python_Python实现字符串匹配算法代码示例的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。