sundayアルゴリズムのpythonは実現します.
1744 ワード
同じ文字列を検索するアルゴリズムです.Sundayは本当にKMPよりずっと簡単です.
理解も簡単です.
下の文字は分かりにくいかもしれません.このブロガーのブログを参考にして、「文字列マッチング——Sundayアルゴリズム」を理解してください.https://blog.csdn.net/q547550831/article/details/51860017 文字列Aがあると仮定して、比較文字列BにAがBを含むかどうかを調べる必要があります.は、Aのi位置とBの0位置を揃え、iは0から開始する. A[i]要素とB[0]が同じであれば、Aの次の要素とBの次の値を比較し続け、lenを比較する.(B)次は、Aの文字列がBであるかどうかを見ることです.終了しました.もちろん、そうではないなら、Bを後ろに移動して、Aの後ろの位置に揃えるべきです.暴力的な方法はBが後ろに移動する度に、Aと比較します.KMP/BM/Sundayはこれらのアルゴリズムは全部変位を計算します.できるだけ多くのスキップします.使用する元素は、比較の回数を減らします. 第二のステップでi＋len(B)−1までの比較過程で位置が異なる場合、直接にA［i＋len(B)］がBにあるかどうかを見に行きます.もし違ったら、何を説明しますか?ここで、i位置に揃うAとBは異なることが分かりました.これでいいです.i＋len(B)BがAのi＋1から始まる位置にあると仮定すれば、A［i＋len(B)］という値は必ずBに表示されます.［i＋len(B)］はBにないので、反証A［i＋1］からA［i＋len(B)］の大きさは間違いなくBを含まずにスキップできます.その後、ステップ1に戻ります. はもちろん、前のステップもA［i＋len(B)］がBの中にあると仮定して、Bの最後からx番目の位置に現れます.i＋1からAの文字列はBを含んでいるかもしれません.ここでは、一歩後に移動しなくてもいいです.直接Aのi＋len(B)を.位置はBのx位置に合わせればいいじゃないですか?この時AはBと同じかどうかを判断します.これはまたステップ3、4に戻り、繰り返します. 終了条件は、AにおいてBが見つかったか、または最後まで見つけられませんでした.最後の部分は、2つの文字列のしっぽがそろっていると比較すればいいです.つまり、len(A)−len(B)の位置です.
理解も簡単です.
下の文字は分かりにくいかもしれません.このブロガーのブログを参考にして、「文字列マッチング——Sundayアルゴリズム」を理解してください.https://blog.csdn.net/q547550831/article/details/51860017 文字列Aがあると仮定して、比較文字列BにAがBを含むかどうかを調べる必要があります.
def sunday_find(src, dst):
len_src = len(src)
len_dst = len(dst)
i = 0
while i < len_src - len_dst + 1:
flag = 0
shift = len_dst
for j in range(0, len_dst):
if src[i+j] != dst[j]:
flag = -1
break
if flag == 0:
return i
p = dst.rfind(src[i+shift])
if p == -1:
shift = len_dst + 1
else:
shift = len_dst - p
i = i + shift
return -1
if __name__ == "__main__":
text = "here_examplfe_v_example"
pattern = "ple"
pos = sunday_find(text, pattern)
print pos