Ponieważ 4 cyfrowa liczba trójkowa posiada największą wartość 2222₍₃₎ = 80₍₁₀₎ 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+1 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 <ctime>

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(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+ 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

# Wyszukiwanie wzorca algorytmem KR
# Data:  13.03.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

import random

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
#----------------------------------------
def h(x):
    hx = 0
    for i in range(M):
        hx = 3*hx+(ord(x[i])-65)
    return hx


# generujemy łańcuch s
s = ""
for i in range(N):
    s += chr(random.randrange(ZP, ZK+1))
# generujemy wzorzec p
p = ""
for i in range(M):
    p += chr(random.randrange(ZP, ZK+1))
# 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, i = 0, 0
while True:
    if (hp == hs) and (p == s[i:i+M]):
        while pp < i:
            print(" ", end="")
            pp += 1
        print("^", end="")
        pp += 1
    i += 1
    if i > N-M: break
    hs = (hs-(ord(s[i-1])-65)*27)*3+\
         ord(s[i+M-1])-65
print()
print()