Name
• String
• Substring
• Search
Edit
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 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];
• 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). Figure 11.1: At each attempt of the Apostolico-Crochemore algorithm we consider a triple (i,j,k).

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