{"conversations": [{"from": "user", "value": "Pots dir-me la idea darrere de l'algoritme de cadena Knuth-Morris-Pratt que coincideixi amb el text?"}, {"from": "assistant", "value": "L' algorisme de cadena Knuth- Morris- Pratt (KMP) \u00e9s un algorisme de temps lineal usat per cercar ocurr\u00e8ncies d' una cadena de patr\u00f3 en una cadena de text. S' ha inventat Donald Knuth, Vaughan Prat, i James Morris al 1977. La idea principal darrere de l' algorisme KMP \u00e9s innecess\u00e0ria per evitar les comparacions sobre el patr\u00f3 que ja s' ha trobat amb la cadena de text. Espec\u00edficament, l' algorisme de precompte a una taula (la funci\u00f3 coneguda com a \" part \" o \" part \") indica que molts car\u00e0cters s' salten en el patr\u00f3 d' una cadena en particular, en comptes de moure la posici\u00f3 de la taula. Per a crear aquesta posici\u00f3, l' algorisme es pot crear una matriu de la primera posici\u00f3 de la columna de cadena de text m\u00e9s llarga (la primera posici\u00f3 de la columna, la que es troba a la columna de la cadena de la que es troba a la cadena de text que es troba a la dreta)."}]}