Python実装文字列マッチングアルゴリズムコード例

文字列マッチングの問題
Pythonでは、長い文字列の中でサブストリングが存在するかどうかを検索するには、strのfind()関数と、find()関数はサブストリングが一致する開始位置のみを返し、なければ-1を返します.2つ目はreモジュールのfindall関数であり、一致するすべてのサブ列を返すことができる.
ただしfindall関数を使用する場合は、文字列に存在する特殊文字に注意する必要があります.
フォース文字列の一致:
テキストの最初のm(モード長)文字にパターンを合わせ、各ペアの対応する文字がすべて一致するか、一致しない文字に遭遇するまで左から右に一致します.後者の場合、モードは右に1ビット移動します.
コードは次のとおりです.

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の先頭文字を整列させ,パターンの最後の文字から比較し,比較に失敗した場合,パターンを後方にシフトさせる.各試行中に比較するのは右から左です.
蛮力アルゴリズムでは,モードの移動ごとに1文字であり,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実装スケジューリングアルゴリズムコードの詳細
Pythonアルゴリズムの図の遍歴
Pythonプログラミングによる蟻群アルゴリズムの詳細
不足点があれば、コメントを歓迎します.友达の本駅に対する支持に感谢します!