エレガントなパイソン

まず、文字列の単純なマッチングを見てみましょう

は、テキスト文字列 s を固定し、整列された部分が完全に同じである場合、パターン文字列 p を整列することとして想像できます。マッチングが成功した場合、パターンは次のようになります。 文字列 p 全体を 1 ビット右に移動し、アライメント部分を確認し続けます。

#Naive match
def naive_match(s, p) ):
m = len(s); n = len(p)
for i in range(m-n+1):#開始ポインタ i
if s[i:i+n] == p:
Yifeng の < ;文字列マッチングのための KMP アルゴリズム>. 最後まで読んだ後、突然明らかになりました
実際には、既知の情報を使用して、パターン文字列 p を前処理して接尾辞と接尾辞の部分一致テーブルを取得することです。右にシフトするビット数を計算します。つまり、kmp = 単純なマッチング + 複数のビットの移動です。詳しくは、Ruan Yifeng の記事を参照してください。ここでは説明しません。


。

#KMP

def kmp_match(s, p):

m = len(s); n = len(p)
cur = 0#開始ポインター cur

table =partial_table(p)

while cur< =m-n:
for i in range(n):
if s[i+cur]!=p[i]:
cur += max(i - table[i-1], 1)# 部分一致テーブルの場合1 ビット右にシフトするだけではなく、一度に複数のビットを移動できます
Break
else:
' ' ' ' ''part ' ' ' ''''から最後まで‐‐ 右へ--- 1 桁から右へ 1 桁
DABD") -> ; [0, 0, 0, 0, 1, 2, 0]'''
prefix = set()
postfix = set ()
ret = [0]
for i in range(1,len(p)) ; ).pop()))
return ret

print naive_match("BBC ABCDAB ABCDABDE", "ABCDABD")
print Partial_table ("ABCDABD")
print kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")



上記はエレガントな Python の内容です。その他の関連コンテンツについては、PHP 中国語 Web サイト (www.php.ん）！