public class BuscaPadroes 
  /** Esta classe contém o algoritmo KMP (Knuth, Morris e Pratt) como 
      descrito no livro de Cormen, Leiserson e Rivest 

      Para usar, compile e execute

       java BuscaPadroes <padrão> <texto> 

  **/
{ 
  static void CalculaApr (int [] Apr, char [] P)
    {
      /* A função CalculaApr constrói o vetor Apr, usado dentro do KMP para 
	 armazenar o valor do máximo que podemos aproveitar do padrão quando 
	 um erro ocorre */

      Apr[0] = -1;
      int k = -1;
      for( int q = 1; q < P.length; q++){
	while(k >= 0 && P[k+1] != P[q])  // enquanto a próxima letra não bate,
	                                 // volta no padrão
	  k = Apr[k];
	if( P[k+1] == P[q]) k++; /* se a letra bateu, anda um
				    caso contrário, k = -1 */
	Apr[q] = k;              // valor de Apr[q] determinado
      }
      //      for( int i = 0; i < P.length; i++) System.out.print(Apr[i]);
      //      System.out.println();
      
    }
  
  static void KMP( char [] T, char [] P)
    {
      /* A idéia do KMP é aproveitar, quando um caractere incorreto é lido, o 
	 máximo possível do padrão correto. Para isso, começamos calculando o 
	 vetor Apr, que é usado durante toda a busca */

      int [] Apr = new int[P.length];
      CalculaApr (Apr, P);
      int q = -1;
      for( int i = 0 ; i < T.length; i++){
	while (q >= 0 && P[q+1] != T[i]) //enquanto a letra não bate...
	  q = Apr[q];
	if( P[q+1] == T[i]) q++; //ou a letra está correta, e andamos no padrão
	                         // ou q é -1
	if(q == P.length - 1){
	  System.out.println("posição "+(i-P.length+1));
	  q = Apr[q];   // ao achar uma ocorrência pode ser que tenha outra
	                // "encavalada"
	}
      }
    }
  
  public static void main( String [] in)
    {
      KMP( in[1].toCharArray(), in[0].toCharArray()); //transforma as strings 
                                                      // em vetores de char
    }
}