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

hash(y[0 .. 7]) = 17819

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

hash(y[1 .. 8]) = 17533

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

hash(y[2 .. 9]) = 17979

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

hash(y[3 .. 10]) = 19389

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

hash(y[4 .. 11]) = 17339

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 2 3 4 5 6 7 8  
  G C A G A G A G  

hash(y[5 .. 12]) = 17597

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

hash(y[6 .. 13]) = 17102

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

hash(y[7 .. 14]) = 17117

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

hash(y[8 .. 15]) = 17678

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

hash(y[9 .. 16]) = 17245

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

hash(y[10 .. 17]) = 17917

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

hash(y[11 .. 18]) = 17723

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

hash(y[12 .. 19]) = 18877

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

hash(y[13 .. 20]) = 19662

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

hash(y[14 .. 21]) = 17885

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

hash(y[15 .. 22]) = 19197

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

hash(y[16 .. 23]) = 16961

The Karp-Rabin algorithm performs 8 character comparisons on the example.

Karp-Rabin algorithm