class Boyer_Moore_Galil 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;

      /* delta2 */
      dd  = new int[m+1];
      dd_ = new int[m+1];
      for (int k = 0; k <= m; k++) dd[k] = dd_[k] = m;
      j = m; t = m + 1;
      while (j > 0) {
        f[j] = t;
        while (t <= m && p[j-1] != p[t-1]) {
          dd_[t] = minimum( dd_[t], t - j ) ;
          t = f[t];
        }
        j--; t--;
        dd[t] = minimum( dd[t], t - j );
      }
      for (int k = 0; k <= t; k++) {
        dd [k] = minimum( dd [k], t ); 
	dd_[k] = minimum( dd_[k], t );
      }
      delta2 = dd_;
    }

    void find(char t[], int n, char p[], int m) throws Exception {
      boolean trivial[] = new boolean[m];
      int     i, j;
      char    c = '0';
      int     memory = 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 > memory; --j) {
          if (stopRequested) return;
          if ((c = t[i+j-1]) != p[j-1]) break;
          cnt++;
          pause(i, trivial, j-1, false, (j==memory+1), cnt);
        }
        if (j == memory) {
	  i += delta2[0];
          memory = m - delta2[0];
        } else {
          cnt++;
          pause(i, trivial, j-1, true, false, cnt);
          i += maximum( delta1[c]-(m-j), delta2[j] );
          memory = 0;
        }
        for (int k=0; k<m; k++) trivial[k] = (k < memory);
      }
    }
}