h ( s  ) = c  × 3 ³ + c  × 3 ² + c  × 3 ¹ + c  × 3 ⁰,
gdzie c  oznacza cyfrę trójkową uzyskaną z liter łańcucha przez odjęcie od ich kodu liczby 65.

Ponieważ 4 cyfrowa liczba trójkowa posiada największą wartość 2222 _{( 3 )} = 80 _{( 10 )} i mieści się bez problemu w 32 bitowym typie całkowitym, zrezygnowaliśmy z arytmetyki modulo.

// Wyszukiwanie wzorca algorytmem KR
// Data:  4.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

const
  N  = 79;  // długość łańcucha s
  M  =  4;  // długość wzorca p
  zp = 65;  // kod pierwszego znaku alfabetu
  zk = 67;  // kod ostatniego znaku alfabetu

// Funkcja obliczająca hasz dla łańcucha x
//----------------------------------------
function h ( x : ansistring ) : integer;
var
  i, hx : integer;
begin
  hx := 0;
  for i := 1 to M do
    hx := 3 * hx + ( ord ( x [ i ] ) - 65 );
  h := hx;
end;

var
  s, p : ansistring;
  pp, i, Hp, Hs : integer;

begin
  randomize;

  // generujemy łańcuch s

  s := '';
  for i := 1 to N do
    s := s + chr ( zp + random ( zk - zp + 1 ) );

  // generujemy wzorzec

  p := '';
  for i := 1 to M do
    p := p + chr ( zp + random ( zk - zp + 1 ) );

  // wypisujemy wzorzec

  writeln ( p );

  // wypisujemy łańcuch

  writeln ( s );

  // obliczamy hasz wzorca

  Hp := h ( p );

  // obliczamy hasz okna wzorca

  Hs := h ( s );

  // szukamy pozycji wzorca w łańcuchu

  pp := 1; i := 1;

  while true do
  begin
    if( Hp = Hs ) and ( p = copy ( s, i, M ) ) then
    begin
       while pp < i do
       begin
         write ( ' ' ); inc ( pp );
       end;
       write ( '^' ); inc ( pp );
    end;
    inc ( i );
    if i = N - M + 2 then break;
    Hs := ( Hs- ( ord ( s [ i-1 ] )-65 )*27 )*3+ord ( s [ i+M-1 ] )-65;
  end;
  writeln;
end.

// Wyszukiwanie wzorca algorytmem KR
// Data:  4.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N  = 79;  // długość łańcucha s
const int M  =  4;  // długość wzorca p
const int zp = 65;  // kod pierwszego znaku alfabetu
const int zk = 67;  // kod ostatniego znaku alfabetu

// Funkcja obliczająca hasz dla łańcucha x
//----------------------------------------
int h ( string & x )
{
  int i, hx;

  hx = 0;
  for( i = 0; i < M; i++ )
    hx = 3 * hx + ( x [ i ] - 65 );
  return hx;
}

int main( )
{

  string s, p;
  int pp, i, Hp, Hs;

  srand ( ( unsigned )time ( NULL ) );

  // generujemy łańcuch s

  s = "";
  for( i = 0; i < N; i++ )
    s += zp + rand( ) % ( zk - zp + 1 );

  // generujemy wzorzec p

  p = "";
  for( i = 0; i < M; i++ )
    p += zp + rand( ) % ( zk - zp + 1 );

  // wypisujemy wzorzec

  cout << p << endl;

  // wypisujemy łańcuch

  cout << s << endl;
  
  // obliczamy hasz wzorca

  Hp = h ( p );

  // obliczamy hasz okna wzorca

  Hs = h ( s );

  // szukamy pozycji wzorca w łańcuchu

  pp = i = 0;

  while( true )
  {
    if( ( Hp == Hs ) && ( p == s.substr ( i, M ) ) )
    {
      while( pp < i )
      {
        cout << " "; pp++;
      }
      cout << "^"; pp++;
    }
    i++;
    if( i == N - M ) break;
    Hs = ( Hs - ( s [ i - 1 ] - 65 ) * 27 ) * 3 + s [ i + M - 1 ] - 65;
  }
  cout << endl;
  return 0;
}

' Wyszukiwanie wzorca algorytmem KR
' Data:  4.07.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Const N  = 79  ' długość łańcucha s
Const M  =  4  ' długość wzorca p
Const zp = 65  ' kod pierwszego znaku alfabetu
Const zk = 67  ' kod ostatniego znaku alfabetu

' Funkcja obliczająca hasz dla łańcucha x
'----------------------------------------
Function h ( Byref x As String ) As Integer

  Dim As Integer i, hx

  hx = 0
  For i = 1 To M
    hx = 3 * hx + Asc ( Mid ( x, i, 1 ) ) - 65
  Next
  h = hx
End Function

Dim As String s, p
Dim As Integer pp, i, Hp, Hs

Randomize

' generujemy łańcuch s

s = ""
For i = 1 To N: s += Chr ( zp + Cint ( Rnd * ( zk - zp ) ) ): Next

' generujemy wzorzec p

p = ""
For i = 1 To M: p += Chr ( zp + Cint ( Rnd * ( zk - zp ) ) ): Next

' wypisujemy wzorzec

Print p

' wypisujemy łańcuch

Print s

' obliczamy hasz wzorca

Hp = h ( p )

' obliczamy hasz okna wzorca

Hs = h ( s )

' szukamy pozycji wzorca w łańcuchu

pp = 1: i = 1

Do
  if( Hp = Hs ) And ( p = Mid ( s, i, M ) ) Then
    While pp < i
      Print " ";: pp += 1
    Wend
    Print "^";: pp += 1
  End If
  i += 1
  If i = N - M + 2 Then Exit Do
  Hs = ( Hs- ( Asc ( Mid ( s, i-1, 1 ) )-65 )*27 )*3+Asc ( Mid ( s, i+M-1, 1 ) )-65
Loop
Print
End