Apostolico-Chrochemore example


First attempt
G C A T C G C A G A G A G T A T A C A G T A C G
  1 2 3  
G C A G A G A G  

Shift by: 4 (i-kmpNext[i]=3- -1)

Second attempt
G C A T C G C A G A G A G T A T A C A G T A C G
  1  
  G C A G A G A G  

Shift by: 1 (i-kmpNext[i]=1-0)

Third attempt
G C A T C G C A G A G A G T A T A C A G T A C G
  8 1 2 3 4 5 6 7  
  G C A G A G A G  

Shift by: 7 (i-kmpNext[i]=8-1)

Fourth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
  1  
  G C A G A G A G  

Shift by: 1 (i-kmpNext[i]=1-0)

Fifth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
  1  
  G C A G A G A G  

Shift by: 1 (i-kmpNext[i]=1-0)

Sixth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
  1  
  G C A G A G A G  

Shift by: 1 (i-kmpNext[i]=1-0)

Seventh attempt
G C A T C G C A G A G A G T A T A C A G T A C G
  1  
  G C A G A G A G  

Shift by: 1 (i-kmpNext[i]=1-0)

Eighth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
  1 2 3 4  
  G C A G A G A G

Shift by: 3 (i-kmpNext[i]=4-1)

The Apostolico-Chrochemore algorithm performs 20 character comparisons on the example.

Apostolico-Chrochemore algorithm