Algoritmo de Knuth-Morris-Pratt

algoritmo.txt

funcao kmp(str, substr, tam_str, tam_substr, aux):

	idx_substr = idx_str = 0

	enquanto idx_str < tam_str:
		se substr[idx_substr] == str[idx_str]:
			idx_substr = idx_substr + 1
			idx_str = idx_str + 1
		se idx_substr == tam_substr:
			"padrao encontrado na pos (idx_str - idx_substr)"
			idx_substr = aux[idx_substr - 1]
		senao se (idx_str < tam_str E substr[idx_substr] != str[idx_str]):
			se idx_substr != 0:
				idx_substr = aux[idx_substr - 1]
			senão:
				idx_str = idx_str + 1


function prefix(substr, tam_substr, aux):

	aux[0] = 0 // aux[0] é sempre 0
	j = 0 // tamanho do maior prefixo que é sufixo
	i = 1

	enquanto i < tam_substr:
		se substr[i] == substr[j]:
			j = j + 1
			aux[i] = j
			i = i + 1
		senão:
			se j != 0:
				j = aux[j - 1]
			senão:
				aux[i] = 0
				i = i + 1