Knuth-Morris-Pratt 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 4  
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]=0- -1)

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
  1 2 3 4 5 6 7 8  
  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]=0- -1)

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]=0- -1)

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]=0- -1)

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  
  G C A G A G A G

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

The Knuth-Morris-Pratt algorithm performs 18 character comparisons on the example.

Knuth-Morris-Pratt algorithm