public class StringMatchKMP {
  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 dopasowania; –1 oznacza brak dopasowania
  public static int match(String text, String pattern) {
    int[] fail = getFailure(pattern);
    int i = 0; // Indeks dla tekstu
    int k = 0; // Indeks dla wzorca
    while (i < text.length()) {
      if (text.charAt(i) == pattern.charAt(k)) {
        if (k == pattern.length() - 1) {
          return i - pattern.length() + 1; // Wzorzec został dopasowany
        }
        i++; // Porównanie następnej pary znaków
        k++;
      }
      else {
        if (k > 0) {
          k = fail[k - 1]; // Dopasowywanie pozycji do przedrostka
        }
        else {
          i++; // Brak pasującego przedrostka
        }
      }
    }

    return -1;
  }
	
  // Obliczanie wartości funkcji niepowodzenia
  private static int[] getFailure(String pattern) {
    int[] fail = new int[pattern.length()];
    int i = 1;
    int k = 0;
    while (i < pattern.length()) {
      if (pattern.charAt(i) == pattern.charAt(k)) {
        fail[i] = k + 1;
        i++;
        k++;
      }
      else if (k > 0) {
        k = fail[k - 1];
      }
      else {
        i++;
      }
    }
    
    return fail;
  }
}
