Name

Edit

**Figure 11.1**: At each attempt of the Apostolico-Crochemore algorithm we consider a triple (i,j,k).

The Apostolico-Crochemore uses the kmpNext shift table (see chapter Knuth, Morris and Pratt algorithm) to compute the shifts.

Let =0 if x is a power of a single character (x=c^m with c in ) and be equal to the position of the first character of x different from x[0] otherwise (*x=a^bu for a, b in , u in * and a ** b*). During each attempt the comparisons are made with pattern positions in the following order: , +1, ... , m-2, m-1, 0, 1, ... , -1.

During the searching phase we consider triple of the form (i, j, k) where:

- the window is positioned on the text factor y[j .. j+m-1];
- 0 k and x[0 .. k-1]=y[j .. j+k-1];
- i < m and x[ .. i-1]=y[j+ .. i+j-1].

The initial triple is (,0,0).

We now explain how to compute the next triple after (i,j,k) has been computed.

Three cases arise depending on the value of i:

i =

If x[i] = y[i+j] then the next triple is (i+1, j, k).If x[i] y[i+j] then the next triple is (, j+1, max{0, k-1}).

< i < m

If x[i] = y[i+j] then the next triple is (i+1, j, k).If x[i] y[i+j] then two cases arise depending on the value of kmpNext[i]:

- kmpNext[i] : then the next triple is (, i+j-kmpNext[i], max{0, kmpNext[i]})
- kmpNext[i] > : then the next triple is (kmpNext[i], i+j-kmpNext[i], )

i =m

If k < and x[k]=y[j+k] then the next triple is (i, j, k+1).

Otherwise either k < and x[k] y[j+k], or k=. If k= an occurrence of x is reported. In both cases the next triple is computed in the same manner as in the case where < i < m.

The preprocessing phase consists in computing the table kmpNext and the integer . It can be done in O(m) space and time. The searching phase is in O(n) time complexity and furthermore the Apostolico-Crochemore algorithm performs at most n text character comparisons in the worst case.

C