Algoritmul Knuth-Morris-Pratt(KMP) pentru potrivirea sirurilor

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.