public class StringMatchBoyerMoore {
  public static void main(String[] args) {
    java.util.Scanner input = new java.util.Scanner(System.in);
    System.out.print("Podaj tekst: ");
    String text = input.nextLine();
    System.out.print("Podaj wzorzec: ");
    String pattern = input.nextLine();
    
    int index = match(text, pattern);
    if (index >= 0)
      System.out.println("Indeks wzorca: " + index);
    else
      System.out.println("Brak dopasowania");
	}

  // Zwraca indeks pierwszego wystąpienia wzorca; –1 oznacza brak dopasowania
  public static int match(String text, String pattern) {
    int i = pattern.length() - 1;
    while (i < text.length()) {
      int k = i;
      int j = pattern.length() - 1;
      while (j >= 0) {
        if (text.charAt(k) == pattern.charAt(j)) {
          k--; j--;
        }
        else {
          break;
        }
      }
    	
      if (j < 0)
        return i - pattern.length() + 1; // Znaleziono wzorzec
    	
      int u = findLastIndex(text.charAt(k), j - 1, pattern);
      if (u >= 0) { // text[k] występuje w pozostałej części wzorca
        i = k + pattern.length() - 1 - u;
      }
      else { // text[k] nie występuje w pozostałej części wzorca
        i = k + pattern.length();
      }
    }

    return -1;
  }
	
  // Zwraca indeks ostatniego elementu z pattern[0 .. j]
  // pasującego do ch; –1 oznacza brak pasujących elementów
  private static int findLastIndex(char ch, int j, String pattern) {
    for (int k = j; k >= 0; k--) {
      if (ch == pattern.charAt(k)) {
        return k;
      }
    }
    
    return -1;
  }
}
