Algoritmos/Reconhecimento de padrões/Algoritmo KMP

Origem: Wikilivros, livros abertos por um mundo aberto.
< Algoritmos‎ | Reconhecimento de padrões
Saltar para a navegação Saltar para a pesquisa

O Algoritmo KMP foi descoberto por Knuth, Morris inicialmente e só foi publicado em 1977 juntamente com Pratt. O algoritmo introduz o conceito de autômato de estados e é usado para busca de cadeias. O KMP é o primeiro algoritmo que tem como pior caso a complexidade de tempo linear O(n). A implementação é complicada e perde em eficiência para o Shift-And e o Boyer-Moore-Horspool. O algoritmo procura a ocorrência de uma palavra ou caractere dentro de um texto e quando aparece uma diferença, a palavra tem em si a informação necessária para determinar onde começar a próxima comparação.

Exemplo[editar | editar código-fonte]

Suponha o Texto: ablwajkmlnop.

O algoritmo começa no primeiro caractere a com 0. Em seguida vai para o próximo caractere b, como na substring ab não há prefixo iguais fica 00. E o algoritmo vai seguindo até encontrar um conflito, quando chega na substring ablwa, o prefixo a já é igual ao sufixo próprio a que termina a substring, ficando 00001.

Funcionamento do KMP
i 0 1 2 3 4 5 6 7 8 9 10 11
Texto a b l w a j k m l n b p
j 0 0 0 0 1 0 0 0 2 0 3 0

Implementação KMP[editar | editar código-fonte]

 public static int kmp(String padrao, String texto) {
 
   int t, p;
   int tamPadrao = padrao.length();
   int tamTexto = texto.length();
   int next[] = new int[tamPadrao];

   iniciar(tamPadrao, padrao, next);

   for( t=0, p=0; p < tamPadrao && t < tamTexto; t++, p++)
	while( (p >= 0) && (texto.charAt(t) != padrao.charAt(p)))
	    p = next[p];

   if (p==tamPadrao)
	return t - tamPadrao;
        else return -1;
        
  }

Código de busca do KMP[editar | editar código-fonte]

O código de busca do KMP é muito parecido com o código da segunda versão do Algoritmo de força bruta.

public int search(String txt) {
   int j, M = pat.length();
   int i, N = txt.length();

   for (i = 0, j = 0; i < N && j < M; i++)
      j = dfa[txt.charAt(i)][j];

   if (j == M) return i - M;
   else return N;
}

Posições de Retrocesso[editar | editar código-fonte]

public static void iniciar(int tam, String padrao, int next[]) {
   int i, j;
       
   next[0] = -1;

   for( i = 0, j = -1; i < tam-1; ) 
     {
	while( (j>= 0) && (padrao.charAt(i) != padrao.charAt(j)) )
	   j = next[j];
       i++; j++;
       if(padrao.charAt(i) == padrao.charAt(j))
          next[i] = next[j];
       else next[i] = j))
     }
   
}

Bibliografia[editar | editar código-fonte]

FEOFILOFF, Paulo. Algoritmo KMP para busca de substring. Acessado em: 23 de maio de 2017.

Pesquisa em String Acessado em: 23 de maio de 2017.

CUPERTINO, Fabiano Botelho; ALMEIDA, Charles Ornelas; ZIVIANI, Nivio. Projeto de Algoritmos. Acessado em: 23 de maio de 2017.