文字列探索 - 一致する文字列の複雑

Question

私は「文字列検索アルゴリズム」の解決しようとしていますが、多くのサイトの答えがO（mは複雑（「ナイーブ文字列検索」のようです（N- KMPもO（n）のので、私は間違いなく間違っている、しかしどこ？

必要がありますがありながら、M + 1））、以下の私のALGOの問題何だ、それは、O（n）との最悪の場合の複雑さを持っています

def find(s1, s2): 
    size = len(s1) 
    index = 0 
    while (index != len(s2)): 
     if s2[index : index + size] == s1: 
      print 'Pattern found at index %s'%(index) 
      index += size 
     else: 
      index += 1 

だから私はs2[index : index + size] == s1がOであると仮定していた両方のハッシュが等しい文字列である場合（1）O（N）であり、ここで私の元の質問になり、

• なぜ等しくなければならない、二つの文字列を計算し、比較のハッシュではありません。
• どうやって衝突するのか分かりません。それはハッシュアルゴリズムに依存しません。 MD5のように既知の改行があります。

Answer 1

オリジナル質問

私はあなたのコードは複雑性O（n）を持っていると思うのではなく、O（MN）。このチェックはs2[index : index + size] == s1です。最悪の場合、len(s1)の文字比較が必要なためです。

をハッシュ

---

Wikipedia's definition of a hash function

ここです：

ハッシュ関数は、固定サイズのデータ​​に 任意のサイズのデータ​​をマッピングするために使用することができる任意の関数です。ハッシュ 関数によって返される値は、ハッシュ値、ハッシュコード、ダイジェスト、または単に ハッシュと呼ばれます。 1つの用途はハッシュテーブルと呼ばれるデータ構造であり、高速データ検索のためにコンピュータソフトウェアで広く使用されている。

ここでは、このアプローチで最初の問題にぶつかります。ハッシュ関数は任意の大きさの値をとり、固定サイズの値を返します。 pigeonhole principleに続いて、複数の値を持つ少なくとも1つのハッシュがあります。簡単な例として、ハッシュ関数が常に1バイト長の出力を生成するとします。つまり、可能な出力は256です。 257アイテムをハッシュした後、同じハッシュを持つアイテムが少なくとも2つあることは常に確実です。これをできるだけ避けるために、良いハッシュ関数は可能な限りすべての可能な出力の入力をuniformlyとしてマップします。

ハッシュが等しくない場合、文字列が等しくないことを確認できますが、逆も同様です。 2つの異なる文字列に同じハッシュを付けることができます。