import java.io.*;

/**
 * Description: The class include basically three Matching Algoritms (Brute 
 * Force, Boyer-Moore, and Knuth-Morris-Pratt) over text and pattern strings 
 * given by the user as an input. The method "main" prints the number returned 
 * by one of the matching algorithms (that is the position in the text where 
 * the pattern occurs, if any, and -1 otherwise) and tests that the algorithms 
 * produce the same result.
 *
 * @author Giuditta Franco
 */

public class TestMatching {

  public TestMatching() {
  }

public static void main(String[] args) {

   BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    String x = null, y = null;

    try {
      System.out.print("Inserire stringa del testo: ");
      x = input.readLine();
      System.out.print("Inserire stringa del pattern: ");
      y = input.readLine();
    } catch (IOException e) {};

    System.out.println("String X: " + x);
    System.out.println("String Y: " + y);
 
   System.out.println("Il pattern occorre nel testo alla posizione: " + BMmatch(x, y) );
   
   int i =  BMmatch(x, y);
   int j =  KMPmatch(x, y);
   int k = BruteForce(x, y);
   if (i==j && j==k){
       System.out.println("I tre algoritmi danno lo stesso risultato");
} else  System.out.println("I tre algoritmi danno un risultato diverso!");
}

public static int BMmatch (String text, String pattern) {
    int[] last = buildLastFunction(pattern);
    int n = text.length();
    int m= pattern.length();
    int i = m-1;
    if (i>n-1)
	return -1; 

// nessuna corrispondenza se il pattern e' piu' lungo del testo

    int j = m-1;
    do {
	if(pattern.charAt(j)==text.charAt(i))
	    if(j==0)
		return i; //corrispondenza
	    else {// l'euristica procede da destra verso sinistra
		i--;
		j--;
	    }
	else { //l'euristica "salta-caratteri"
	    i=i+m-Math.min(j, 1+last[text.charAt(i)]);
	    j=m-1;
	}
    } while (i<=n-1);
    return -1; //nessuna corrispondenza
}

public static int[] buildLastFunction (String pattern) {
    int[] last = new int[128]; // si inizializza con tutti i caratteri ASCII
    for (int i=0; i<128; i++) {
	last[i]= -1; //inizializzazione dell'array
    }
    for (int i=0; i < pattern.length(); i++){
	last[pattern.charAt(i)] = i; //un cast implicito per il codice ASCII intero
    }
    return last;
} 


public static int KMPmatch (String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] fail = computeFailFunction(pattern);
    int i=0;
    int j = 0;
    while (i<n){
	if (pattern.charAt(j) == text.charAt(i)) {
	    if (j== m-1)
		return i-m +1; // abbinamento
	    i++;
	    j++;
	}
	else if (j>0)
	    j = fail[j-1];
	else i++;
    }
    return -1; // nessun abbinamento
}

public static int[] computeFailFunction (String pattern) {

    int [] fail = new int[pattern.length()];

    fail[0]=0;

    int m = pattern.length();
    int j = 0;
    int i = 1;
    while (i<m) {
	if (pattern.charAt(j)==pattern.charAt(i)){ //j+1 caratteri corrispondenti
	    fail[i]=j+1;
	    i++;
	    j++;
	}
	else if (j>0) // j segue un prefisso corrispondente
	    j = fail[j-1];
	else { //nessuna corrispondenza
	    fail[i]=0;
	    i++;
	}
    }
    return fail;
}

public static int BruteForce (String text, String pattern) {
    int n = text.length();
    int m = pattern.length();

 for (int i=0; i <= n-m; i++) {
     int j=0;
     while (j<m && text.charAt(i+j)==pattern.charAt(j)) {
	 j++;
	 if(j==m) {
	     return i;
	 }
     }

 }
  return -1;  
}

}