Algorimul Knuth-Morris-Pratt - Sisteme Informatice

Extras din document

Algoritmul Knuth-Morris-Pratt reprezinta o metoda avansata de cautare a unui sir de caractere – model(pattern) P[0..m] intr-un sir de caractere sursa T[0..n], evident n>=m. T[0..n] Construit pe functia-prefix π(P), algoritmul este un exemplu clasic de programare dinamica, cu eficienta nu de O(N*M), ci de O(N+M). Spre deosebire de metodele liniare, algoritmul KMP propune ca deplasarea modelului P de-a lungul sursei T sa fie efectuata cu un numar mai mari de pozitii si ca in acelasi timp sa se memoreze partea de text care coincide cu modelul. Acest lucru ne va permite sa evitam comparatiile inutile si, astfel, va creste considerabil viteza de cautare. ...