private void fail(String pat) {
      int n = pat.length();
      failure[0] = -1;
      for (int j = 1; j < n; j++) {
        int i = failure[j - 1];
        while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0)
          i = failure[i];
        if (pat.charAt(j) == pat.charAt(i + 1))
          failure[j] = i + 1;
        else
          failure[j] = -1;
      }
    }