• 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 Knuth-Morris-Pratt(KMP) pentru potrivirea sirurilor

1
  • Publicat de Andrei Avădănei
  • în C/C++ · Tehnic
  • — 16 nov., 2009 at 10:00 am

In urma cu ceva vreme am propus o problema ce are o aplicabilitate si o importanta extrem de mare in informatica si in aplicatiile ce lucreaza 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) pentru a cauta potriviri.

Am promis atunci ca vom continua prezentarea unui nou algoritm si anume unul din cele mai bune algoritme de cautare a subsirurilor intr-un sir, avand o complexitate aproape liniara.

Cum lucreaza acest algoritm?
Acest algoritm se bazeaza pe un pas foarte important si anume generarea prefixului. Functia buildPrefix calculeaza un vector L cu m componente, in care L[p] este lungimea celui mai lung prefix strict al lui P[1..p] care este si sufix strict al lui P[1..p]. Lungimea L[p] va fi calculata in functie de L[p-1]. Vectorul L este foarte important pentru algoritmul KMP.
Sa consideram un sir S[1..s].Algoritmul Knuth Morris Pratt (KMP) gaseste eficient toate aparitiile unui sir model P[1..m] intr-un sir T[1..n], folosindu-se de rezultatele recent calculate in vectorul L.

Numim prefix de lungime k al sirului S[1..s] subsirul format din caracterele S[1], S[2]… S[k-1], S[k], notat S[1..k].
Numim sufix de lungime k al sirului S[1..s] subsirul format din caracterele S[s-k+1], S[s-k+2]… S[s-1], S[s] notat S[s-k+1..s].
Un prefix de lungime k al lui S[1..s] este sufix de lungime k al lui S[1..s] daca S[1..k] = S[s-k+1..s].
Un prefix al unui sir este strict daca lungimea sa este strict mai mica decat lungimea sirului.

Daca doriti cateva exemple dinamice ce se bazeaza prin imagini al acestui algoritm puteti accesa linkurile de mai jos:

Problema potrivirii sirurilor
Cautare pe siruri – Algoritmul KMP
Algoritmul KMP – cautari traduse
Automate finite si KMP

O implementare a acestui algoritm privind problema Potrivirii sirurilor, obtine 100 de puncte folosind algoritmul KMP.
Descarca solutia si implementarea algoritmului KMP.

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: KMPKnuth-Morris-Prattpotrivirea sirurilorRabin-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 Problema Numar
  • Articolul următor Accesul la informatii ar trebui sa fie liber

1 Comentariu

  1. ale_alee spune:
    iulie 20, 2011 la 5:55 am

    esti de milioane…m-ai salvat cu chestiunea asta.ms 🙂


  • 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 Knuth-Morris-Pratt(KMP) 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.