快捷導(dǎo)航

Python實(shí)現(xiàn)字符串匹配算法代碼示例

更新時(shí)間：2017年12月05日 16:31:07 作者：老衲很淡定

這篇文章主要介紹了Python實(shí)現(xiàn)字符串匹配算法代碼示例，涉及字符串匹配存在的問(wèn)題，蠻力法字符串匹配，Horspool算法，具有一定參考價(jià)值，需要的朋友可以了解下。

字符串匹配存在的問(wèn)題

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

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

蠻力法字符串匹配：

將模式對(duì)準(zhǔn)文本的前m（模式長(zhǎng)度）個(gè)字符，然后從左到右匹配每一對(duì)對(duì)應(yīng)的字符，直到全部匹配或遇到一個(gè)不匹配的字符。后一種情況下，模式向右移一位。

代碼如下：

def string_match(string, sub_str): 
 # 蠻力法字符串匹配 
 for i in range(len(string)-len(sub_str)+1): 
  index = i  # index指向下一個(gè)待比較的字符 
  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)，事實(shí)上，該算法的平均效率比最差效率好得多。事實(shí)上在查找隨機(jī)文本的時(shí)候，其屬于線性的效率Θ(n)。

Horspool算法：

Horsepool算法是Boyer-Moore算法的簡(jiǎn)化版本，這也是一個(gè)空間換時(shí)間的典型例子。算法把模式P和文本T的開(kāi)頭字符對(duì)齊，從模式的最后一個(gè)字符開(kāi)始比較，如果嘗試比較失敗了，它把模式向后移。每次嘗試過(guò)程中比較是從右到左的。

在蠻力算法中，模式的每一次移動(dòng)都是一個(gè)字符，Horspool算法的核心思想是利用空間來(lái)?yè)Q取時(shí)間，提升模式匹配窗口的移動(dòng)幅度。與蠻力算法不同的是，其模式的匹配是從右到左的，通過(guò)預(yù)先算出每次移動(dòng)的距離并存于表中。

代碼如下：

__author__ = 'Wang' 
from collections import defaultdict 
def shift_table(pattern): 
 # 生成 Horspool 算法的移動(dòng)表 
 # 當(dāng)前檢測(cè)字符為c，模式長(zhǎng)度為m 
 # 如果當(dāng)前c不包含在模式的前m-1個(gè)字符中，移動(dòng)模式的長(zhǎng)度m 
 # 其他情況下移動(dòng)最右邊的的c到模式最后一個(gè)字符的距離 
 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): 
 # 實(shí)現(xiàn) horspool 字符串匹配算法 
 # 匹配成功，返回模式在text中的開(kāi)始部分；否則返回 -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)。在查找隨機(jī)文本的時(shí)候，其屬于線性的效率Θ(n)。雖然效率類(lèi)型相同，但平均來(lái)說(shuō)，Horspool算法比蠻力算法快很多。

總結(jié)

以上就是本文關(guān)于Python實(shí)現(xiàn)字符串匹配算法代碼示例的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站：

Python實(shí)現(xiàn)調(diào)度算法代碼詳解

Python算法之圖的遍歷

Python編程實(shí)現(xiàn)蟻群算法詳解

如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！

您可能感興趣的文章: