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[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]; 
  •  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