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: 3 (i-mpNext[i]=3-0)

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

Shift by: 1 (i-mpNext[i]=0- -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 2 3 4 5 6 7 8  
  G C A G A G A G  

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

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

Ninth 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-mpNext[i]=0- -1)

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

Morris-Pratt algorithm