A Rabin-Karp algoritmus magyarázata

A Rabin-Karp algoritmus egy karakterlánc-illesztési / keresési algoritmus, amelyet Michael O. Rabin és Richard M. Karp fejlesztett ki. Ez használ hash technika és a nyers erő az összehasonlítás, és egy jó jelölt plágium.

Fontos kifejezések

  • A minta a keresendő karakterlánc. Tekintsük a minta hosszát M karakterként.
  • a szöveg az egész szöveg, amelyből a mintát meg kell keresni. Tekintsük a szöveg hosszát N karakterként.

Mi a durva erő összehasonlítása?

A nyers erő összehasonlításában a minta minden karakterét összehasonlítják a szöveg minden karakterével, amíg nem találnak nem megfelelő karaktereket.

Hogyan működik a Rabin-Karp algoritmus

  1. Számítsa ki a minta hash értékét
  2. Számítsa ki a szöveg első M karakterének kivonatolási értékét
  3. Hasonlítsa össze mindkét hash értéket
  4. Ha nem egyenlők, számítani hash érték mellett M karaktereiből szöveget , és hasonlítsa össze újra.
  5. Ha egyenlőek, végezzen durva erő-összehasonlítást.
hash_p = hash value of pattern hash_t = hash value of first M letters in body of text do if (hash_p == hash_t) brute force comparison of pattern and selected section of text hash_t= hash value of next section of text, one character over while (end of text or brute force comparison == true)

Előny a Naiv String Matching Algorithm-mel szemben

Ez a technika csak egy összehasonlítást eredményez szöveges részsorozatonként, és nyers erő csak akkor szükséges, ha a kivonatértékek megegyeznek.