Zhu-Takaoka algorithm

• variant of the Boyer-Moore algorithm;
• uses two consecutive text characters to compute the bad-character shift;
• preprocessing phase in O(m+sigma²) time and space complexity;
• searching phase in O(mn) time complexity.

Zhu and Takaoka designed an algorithm which performs the shift by considering the bad-character shift (see chapter Boyer-Moore algorithm) for two consecutive text characters.

During the searching phase the comparisons are performed from right to left and when the window is positioned on the text factor y[j .. j+m-1] and a mismatch occurs between x[m-k] and y[j+m-k] while x[m-k+1 .. m-1]=y[j+m-k+1 .. j+m-1] the shift is performed with the bad-character shift for text characters y[j+m-2] and y[j+m-1]. The good-suffix shift table is also used to compute the shifts.

The preprocessing phase of the algorithm consists in computing for each pair of characters (a, b) with a, b in Sigma the rightmost occurrence of ab in x[0 .. m-2].

For a,b in Sigma: ztBc[a, b]=k iff

k<m-2 and x[m-k .. m-k+1]=ab and ab does not occur in x[m-k+2 .. m-2]

or

k=m-1 and x[0]=b and ab does not occur in x[0 .. m-2]

or

k=m and x[0] neq b and ab does not occur in x[0 .. m-2]

It also consists in computing the table bmGs (see chapter Boyer-Moore algorithm).

The preprocessing phase is in O(m+sigma²) time and space complexity. The searching phase has a quadratic worst case.

 void preZtBc(char *x, int m, int ztBc[ASIZE][ASIZE]) {
 int i, j;
 for (i = 0; i < ASIZE; ++i)
 for (j = 0; j < ASIZE; ++j)
 ztBc[i][j] = m;
 for (i = 0; i < ASIZE; ++i)
 ztBc[i][x[0]] = m - 1;
 for (i = 1; i < m - 1; ++i)
 ztBc[x[i - 1]][x[i]] = m - 1 - i;
}
void ZT(char *x, int m, char *y, int n) {
 int i, j, ztBc[ASIZE][ASIZE], bmGs[XSIZE];
 /* Preprocessing */
 preZtBc(x, m, ztBc);
 preBmGs(x, m, bmGs);
 /* Searching */
 j = 0;
 while (j <= n - m) {
 i = m - 1;
 while (i < m && x[i] == y[i + j])
 --i;
 if (i < 0) {
 OUTPUT(j);
 j += bmGs[0];
 }
 else
 j += MAX(bmGs[i],
 ztBc[y[j + m - 2]][y[j + m - 1]]);
 }
}

• ZHU R.F., TAKAOKA T., 1987, On improving the average case of the Boyer-Moore string matching algorithm, Journal of Information Processing 10(3):173-177.