== include(page="template/taskheader" task_id="pmk") ==

Algoritmul KMP este folosit pentru a cauta eficient aparitiile unui cuvant intr-un text. In prima faza el calculeaza functia prefix pentru cuvant. Functia prefix se calculeaza pentru orice prefix al cuvantului.

Algoritmul KMP este folosit pentru a cauta eficient aparitiile unui cuvant intr-un text.
In prima faza el calculeaza functia prefix pentru cuvant. Functia prefix se calculeaza pentru orice prefix al cuvantului.

Pentru un sir ea are ca rezultat lungimea celui mai lung prefix propriu care este si sufix (propriu) al sirului. Un prefix propriu al unui sir e un prefix diferit de sir (sirul intreg nu e prefix propriu).
Ca si conventie de implementare, rezultatul functiei prefix retinut pe pozitia **i** este functia pentru prefixul de la prima pozitia pana la pozitia **i** **exclusiv**, iar pentru prima pozitie se considera ca functia returneaza -1. Un exemplu de functie prefix poate fi urmatorul: