class Knuth_Morris_Pratt extends PatternMatchingAlgorithm {
    public int next[];

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

      j = 0; t = -1; next[0] = -1;
      while (j < m) {
        while (t >= 0 && p[j] != p[t]) t = next[t];
        t++; j++;
	if (j < m && p[j] == p[t]) next[j] = next[t]; 
        else                       next[j] = t;
      }
//for (j=0; j <= m; j++)System.out.println("next[" + j + "] = " + next[j]);
    }

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

      preprocess(p,m);

      clear_table(trivial, m);
      pause(0, trivial, -1, false, false, cnt);
      j = 0; 
      for (i = 0; i < n; i++) {
        while (j == m || (j >= 0 && p[j] != t[i])) {
          if (j < m) cnt++;
          if (stopRequested) return;
          if (j < m) pause(i-j, trivial, j, true, false, cnt);
          j = next[j];
          for (int k = 0; k < m; k++) trivial[k] = (k < j);
          pause(i-j, trivial, -1, false, false, cnt);
        }
        if (j >= 0) {
          cnt++;
          pause(i-j, trivial, j, false, (j+1==m), cnt);
        }
        ++j;
      }
    }
}