public class KMP {

  // Step 0. Naive search, using two nested loops.

  public static int search00 (String pattern, String text)
  {
    final int m = pattern.length();
    final int n = text.length();
    loop: for (int base = 0; base + m <= n; base++) {
      for (int j = 0; j < m; j++)
        if (pattern.charAt(j) != text.charAt(base + j))
          continue loop;
      return base;
    }
    return -1;
  }

  // Step 1. Naive search, using a single loop.

  // The variable base in the previous version is replaced with k;
  // they are related by the equation k == base + j.


  public static int search01 (String pattern, String text)
  {
    final int m = pattern.length();
    final int n = text.length();
    int j = 0, k = 0;
    while (true) {
      if (j == m)
        // End of the pattern reached: success.
        return k - j;
      if (k == n)
        // End of the text reached: failure.
        return -1;
      if (pattern.charAt(j) == text.charAt(k)) {
        // Character match. Advance.
        k++;
        j++;
      }
      else {
        // Character mismatch. Backtrack.
        k = k - j + 1;
        j = 0;
      }
    }
  }

}