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

Algoritmul KMP este folosit pentru a cauta eficient aparitiile un cuvant intr-un text. In prima faza el calculeaza functia prefix pentru cuvant. Functia prefix se calculeaza pentru orice prefix al cuvantului si are ca rezultat lungimea celui mai lung prefix care este si sufix al prefixului curent. Nu se ia in considerare ca prefix sau sufix sirul intreg (ci doar prefixe si sufixe proprii). Ca si conventie de implementare, functia prefix de pe pozitia i calculeaza functia pentru prefixul de la prima pozitia pana la pozitia i **exclusiv**, iar pentru prima pozitie se considera ca funtia returneaza -1. Un exemplu de functie prefix poate fi urmatorul:

Algoritmul KMP este folosit pentru a cauta eficient aparitiile un cuvant intr-un text. In prima faza el calculeaza functia prefix pentru cuvant. Functia prefix se calculeaza pentru orice prefix al cuvantului si are ca rezultat lungimea celui mai lung prefix care este si sufix al prefixului curent. Nu se ia in considerare ca prefix sau sufix sirul intreg (ci doar prefixe si sufixe proprii). 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 funtia returneaza -1. Un exemplu de functie prefix poate fi urmatorul:

 
abbaabbbba
-1 0 0 0 1 1 2 3 0 0
 |_.
 
table(example). |_. a |_. b |

| **i**
| 0
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| **sir[i]** | **a** | **b** | **b** | **a** | **a** | **b** | b | b | b | a |
| **prefix[i]**

| -1
| 0

|

| 0
| 0
| 1
| 1
| 2
| 3
| 0
| 0
|
prefix [6] = prefix("abbaab") = 2 = lungime("ab")

h2. Date de intrare
Fişierul de intrare $pmk.in$ ...