public class BuscaPadroes2 
  /** Esta classe contém os algoritmos KMP (Knuth, Morris e Pratt) e 
      Boyer-Moore como descritos no livro de Cormen, Leiserson e Rivest 

      Para usar, compile e execute

       java BuscaPadroes <padrão> <texto> <alfabeto> 

      O programa imprimirá todas as ocorrências do padrão no texto. 
      Primeiro usando o algoritmo KMP e depois usando o algoritmo Boyer-Moore. 

  **/
{ 
  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"
	}
      }
    }
  static int posicao (char c, char [] A)
    {
      int i = 0;
      while( i < A.length && A[i] != c) i++;
      return(i);
    }
  static int max (int i, int j)
    {
      if(i > j) return(i);
      else return(j);
    }
  static void CalculaMauCaractere(int [] v, char [] P, char [] A)
    {
      int i;
      for( i = 0; i < A.length; i++) v[i] = -1;
      /* implementei o alfabeto como um vetor de char... Ok, ok, não é
	 a solução mais limpa, mas serve pros nossos propósitos. */
      for( i = 0; i < P.length; i++) v[posicao(P[i], A)] = i;
    }
  static void CalculaBomSufixo(int [] v, char [] P)
    {
      int [] pi = new int[P.length];
      int [] pil= new int[P.length];
      char [] Pr= new char[P.length];

      /* inverte o padrão P */
      for( int i = 0; i < P.length; i++) Pr[P.length-1-i] = P[i];
      
      /* calcula o vetor Apr para o padrão e seu inverso */
      CalculaApr(pi, P);
      CalculaApr(pil, Pr);
      
      int j;
      
      /* calcula a posição da última letra (deslocamento default) */
      for(j = 0; j <= P.length; j++) v[j] = P.length - (pi[P.length-1]+1);

      for(int l = 0; l < P.length; l++){

	/* achou um sufixo do padrão no meio do mesmo */
	j = (P.length - (pil[l]+1)) - 1;
	
	/* neste caso o deslocamento deve ser corrigido */
	if( v[j+1] > l - (pil[l]+1)) 
	  v[j+1] = l - (pil[l]+1);
      }
    }
  
      
  static void Boyer_Moore( char [] T, char [] P, char [] A)
    {
      int [] MauCaractere = new int[A.length];
      int [] BomSufixo = new int[P.length + 1];

      /* Se T[s+j] != P[j], então podemos avançar s de 
	 BomSufixo[j+1]. Ou seja, BomSufixo[j+1] é dado por 
         m - max{k : 0 <= k < m+1 e P[j+1..m] é similar a P_k} */

      int j;
			       
      /* os dois vetores vão auxiliar a descobrir os deslocamentos */

      CalculaMauCaractere(MauCaractere, P, A);
      CalculaBomSufixo(BomSufixo, P);     
      
      int s = 0;
      while(s <= T.length - P.length){
	// a verificação do padrão é feita de trás para frente 
	for( j = P.length-1; j >= 0 && P[j] == T[s+j]; j--);
	if(j == -1){
	  System.out.println("posição "+s);
	  s = s + BomSufixo[0];
	}
	else // deslocamento dado como o máximo das duas heurísticas 
	  s = s + max(j - MauCaractere[posicao(T[s+j], A)], BomSufixo[j]);
      }
    }
  

  
  public static void main( String [] in)
    {
      System.out.println("KMP");
      KMP( in[1].toCharArray(), in[0].toCharArray()); /*transforma as strings 
						        em vetores de char */
      System.out.println("Boyer_Moore");
      Boyer_Moore(in[1].toCharArray(), in[0].toCharArray(), in[2].toCharArray());
      
    }
}