• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Algoritmul Rabin-Karp pentru potrivirea sirurilor

3
  • Publicat de Andrei Avădănei
  • în C/C++
  • — 12 aug., 2009 at 12:54 pm

rabin1Potrivirea sirurilor este o problema destul de mare si are o aplicabilitate imensa in domeniul IT si nu numai.Aceasta problema insa a fost abordata de multe persoana ajungandu-se la solutii foarte eficiente.Putem spune ca sunt folosite in algoritmii intellisense, sintax highlighiting , pattern match, etc.

Problema

Se dau doua siruri S si P, se cere gasirea tuturor aparitiilor sirului P in sirul S.Fisierul sir.in contine pe pe prima linia sirul P iar pe a doua sirul S, fisierul de iesire sir.out va avea pe prima linie pozitiile in ordine crescatoare unde se gasesc potriviri.

Exemplu :
sir.in

ABA
CABBCABABAB

sir.out

2
5 7

O abordare naiva ar fi sa incercam pentru fiecare pozitie din sirul S sa gasim o potrivire a sirului P la fiecare pas.In cazul in care nu vom gasi ne vom deplasa un pas mai in fata.Aceasta abordare necesita o parcurgere intr-un timp patratic ( O(|S|*|P|) ) si implicit nu va duce la punctajele maxime ale problemelor abordate.
Solutia folosind algoritmul naiv de potrivire a sirurilor

O solutie mult mai eficienta a acestui algoritm consta in rezolvarea in timp liniar folosind algoritmul Rabin-Karp, ce are la baza hashuri.Acest algoritm are timpul de executie O(|S|+|P|).

Cum lucreaza acest algoritm?
Practic vom construi initial hash-ul patternului P si in acelasi timp a primelor |P| caractere din S.Ne putem folosi de faptul ca orice caracter are o reprezentare decimala.La fiecare pas i vom compara valoarea hash a patternului cu valoarea hash a |P| caractere din S.Daca acestea doua sunt echivalente vom considera ca avem o posibila potrivire la pasul i.Pentru a ne deplasa,pur si simplu vom elimina primul caracter si vom adauga unul in partea dreapta.
Exemplu :

cde – sirul P
abcdef – sirul S

Pasul i = 0 : hash(cde) != hash(abc) -> nu este potrivire , i++
Pasul i = 1 : hash(cde) != hash(bcd) -> nu este potriivre , i++
Pasul i = 2 : hash(cde) == hash(cde) -> potrivire , i++
Pasul i = 3 : hash(cde) != hash(def) -> nu este potriivre ,i++
STOP.

Intrebarea este cum vom elimina un caracter dintr-o valoare hash si cum vom adauga un alt caracter la acel hash?
Pentru a pastra unicitatea la fiecare pas vom inmulti intreg hash`ul cu o baza,dupa care vom adauga caracterul nou.Pentru ca aceasta valoare poate fi imensa ne vom folosi de o tehnica clasica a hash`urilor, aceasta valoare supunand`o la o reducere printr`un modul.

Pentru a construi hashul initial va trebui sa lucram asemanator ca mai jos :

hashi = (hashi-1 * baza + P[i]) % MODUL; // MODUL va avea regulile specifice unei valori de la hashuri,sa nu fie o putere a lui 2 si sa fie cat mai departe de 2 puteri ale acestui numar.

Cum stergem un caracter si cum adaugam un alt caracter la hash?

hashpos+1 = ((hashpos – (S[pos] * VV) % MODUL + MODUL) * baza + S[pos+|P|]) % MODUL; // unde pos este pozitia de inceput a subsirului, VV = (VV*baza)%MODUL, de |P| ori

Cei care stiu hash`uri isi vor pune urmatoarea intrebare : Ce se intampla cu coliziunile?Intradevar, folosind metodele de hashing + reducerea valorilor prin module vom avea riscul sa apara coliziuni.In aceasta situatie este bine sa lucram pe 2 hash`uri,astfel construim cate 2 hash`uri la fiecare subsir si daca ambele sunt potrivite atunci consideram o potrivire la pasul pos.

Solutie folosind algoritmul de potrivire a sirurilor Rabin-Karp

Un alt algoritm ce este folosit pentru potrivirea sirurilor este algoritmul Knuth-Morris-Pratt(KMP) dar acesta va fi prezentat intr-o lectie viitoare. 😀

Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!

Etichete: algoritmicapotrivirea sirurilorprogramareRabin-Karp

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Caffeine Search
  • Articolul următor Problema Gard

3 Comentarii

  1. Andrei Misarca spune:
    august 14, 2009 la 5:59 pm

    Un algoritm foarte folositor si bine explicat, insa lipseste un mic detaliu, fara de care implementarea poate deveni un calvar.
    Ce reprezinta defapt acel hash? Sa zicem ca am cuvantul format din literele ABCDEF…Z. El este format din N litere sa zicem.
    Practic hashul nost’ reprezinta A*P^(N-1) + B*P^(N-2) + C*P(N-3) + … + Y*P + Z modulo ceva. Si acum sa zicem ca vreau sa elimin A si sa mai adaug o litera, sa zicem U. Practic din hash scad A*P^(N-1), P^(N-1) reprezentand exact acel H1 din sursa lui Andrei de mai sus iar hashul devine B*P^(N-2) + C*P^(N-3) + … + Z. Urmatorul pas este sa inmultesc totul cu P si sa adaug U, iar treaba devine B*P^(N-1) + C*P^(N-2) + … + Z*P + U, de zici rezultand si corectitudinea algoritmului (evident pot aparea si acele cazuri de coliziune despre care a specificat Andrei in articol).

  2. Avadanei Andrei spune:
    august 14, 2009 la 6:01 pm

    Am omis doar situatia in care se va adauga un nou caracter in hash, dar am presupus ca se subintelege din crearea hash`ului pentru pattern.Multumesc de completare. 🙂

  3. Algoritmul Knuth-Morris-Pratt(KMP) pentru potrivirea sirurilor | WorldIT spune:
    noiembrie 16, 2009 la 10:04 am

    […] cu siruri de caractere si anume potrivirea unui subsir.Am prezentat doua solutii in legatura cu potrivirea sirurilor : algoritmul naiv de potrivire a sirurilor si un algoritm ce se foloseste de hashuri(Rabin-Karp) […]


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    • imacoolat-curat.ro
      | Published: februarie 3, 2020 - 2:00 am
    • hotel-palace.ro
      | Published: februarie 2, 2020 - 2:00 am
    • www.tahometru.ro
      | Published: februarie 1, 2020 - 2:00 am
    • alexisart.ro
      | Published: ianuarie 30, 2020 - 2:00 am
    • justshop.ro
      | Published: ianuarie 29, 2020 - 2:00 am
    RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • ianuarie 2021
    L Ma Mi J V S D
    « dec.    
     123
    45678910
    11121314151617
    18192021222324
    25262728293031
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Algoritmul Rabin-Karp pentru potrivirea sirurilor
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons

Multumim foarte mult ca ne-ai raportat greseala! O vom remedia in cel mai scurt timp posibil.