{"conversations": [{"from": "human", "value": "Esango didazu Knuth-Morris-Pratt algoritmoaren atzean dagoen ideia?"}, {"from": "gpt", "value": "knuth-Morris-Pratt (KMP) algoritmoa bat duen katea testu-kate bateko agerpenak bilatzeko erabiltzen den algoritmo lineala da. Donald Knuth, Vaughan Pratt- ek asmatu zuen, eta James Morris-ek 1977. KMP algoritmoaren atzeko ideia nagusia derrigorrezko konparazioa ekiditzea da, testu- katearekin bat datorren ereduaren kateari buruzko informazioa lortuz. Bereziki, \"fuluture\" edo \"mber\" taula ezagutzen den bezala, hau da, karaktere- katean zenbat karaktere saltatu behar diren adierazten du, eta ez da behar bezala mugitu kate- katea baten luzera. Bestela, kate bat sortzen du karaktere- barrutiaren aurreneko lerroan, eta kateko posizioaren katean duen katea bat sortzen du. Bestela, karaktere- katea bat sortzen duen katea bat sortzen du karaktere- barrutiaren katearekin."}]}