Explica principiul de funcționare al algoritmului de căutare a subșirurilor Knuth-Morris-Pratt.
sobes.tech AI
Răspuns de la AI
Algoritmul Knuth-Morris-Pratt (KMP) este conceput pentru a căuta o subșir într-un șir în timp liniar, evitând comparațiile repetate de caractere.
Ideea principală este de a calcula în prealabil pentru subșir un array de funcții de prefix (sau "array π"), care arată câți caractere coincid cu începutul subșirului în cazul unei comparații nereușite. Acest lucru permite, în cazul unei nepotriviri, să nu te întorci la începutul șirului original, ci să deplasezi subșirul cu un număr optim de poziții.
Exemplu:
- Text: "ABABDABACDABABCABAB"
- Căutând subșirul: "ABABCABAB"
Algoritmul construiește mai întâi funcția de prefix pentru subșir, apoi parcurge textul comparând caracterele. În cazul unei nepotriviri, folosește funcția de prefix pentru a determina de la care caracter al subșirului să continue compararea, fără a începe de la început.
Acest lucru asigură o complexitate de O(n + m), unde n este lungimea textului, m lungimea subșirului, fiind mai eficient decât căutarea naivă.