class Horspool extends PatternMatchingAlgorithm {
    public int delta1[];
    public int delta2[];
    public int dd_[];
    public int dd [];

    public void preprocess(char p[], int m) {
      int j, t;
      int f[] = new int[m+1];

      /* delta1 */
      delta1 = new int[256];
      for (int q = 0; q < 256; q++) delta1[q] = m;
      for (int i = 1; i < m; i++) delta1[p[i-1]] = m - i;
    }

    void find(char t[], int n, char p[], int m) throws Exception {
      boolean trivial[] = new boolean[m];
      int     i, j;
      char    c = '0';
      int     cnt = 0;

      preprocess(p,m);

      clear_table(trivial, m);
      for (i = 0; i + m <= n; ) {
        pause(i, trivial, -1, false, false, cnt);
        for (j = m; j > 0; --j) {
          if (stopRequested) return;
          if ((c = t[i+j-1]) != p[j-1]) break;
          cnt++;
          pause(i, trivial, j-1, false, (j==1), cnt);
        }
	if (j != 0) {
	    cnt++;
	    pause(i, trivial, j-1, true, false, cnt);
	}
	i += delta1[c];
      }
    }
}