Algoritmos/Reconhecimento de padrões/Algoritmo KMP

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

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

 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

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

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

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.