Explique o princípio de funcionamento do algoritmo de busca de substrings de Knuth-Morris-Pratt.

O algoritmo de Knuth-Morris-Pratt (KMP) destina-se a procurar uma substring numa string em tempo linear, evitando comparações repetidas de caracteres.

A ideia principal é calcular previamente para a substring um array de funções de prefixo (ou "array π"), que mostra quantos caracteres coincidiram com o início da substring numa comparação falhada. Isto permite, em caso de não coincidência, não regressar ao início na string original, mas deslocar a substring pelo número ótimo de posições.

Exemplo:

• Texto: "ABABDABACDABABCABAB"
• Procurando a substring: "ABABCABAB"

O algoritmo primeiro constrói a função de prefixo para a substring, depois percorre o texto comparando os caracteres. Em caso de não coincidência, usa a função de prefixo para determinar a partir de qual carácter da substring continuar a comparação, sem começar do início.

Isto garante uma complexidade de O(n + m), onde n é o comprimento do texto, m é o comprimento da substring, sendo mais eficiente do que a busca ingênua.