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

<html>
  <head>
    <title>
      KR
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>Wyszukiwanie wzorca<br>
          algorytmem KR</b><br/>
          &nbsp;
          (C)2026 mgr Jerzy Wałaszek
          &nbsp;&nbsp;
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B2"
          onclick="main()">
          <hr>
          <b>Wyniki:</b>
          <div align="center">
            <table
            border="0"
            cellpadding="4"
            style="border-collapse:
                   collapse">
              <tr>
                <td id="out">
                  &nbsp;
                </td>
              </tr>
            </table>
          </div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

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

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

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

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

function main()
{
  var s, p, pp, i, Hp, Hs, t;

  // generujemy łańcuch s
  s = "";
  for(i = 0; i < N; i++)
    s += String.fromCharCode
        (zp + Math.floor(
        Math.random() *
        (zk - zp + 1)));

  // generujemy wzorzec p
  p = "";
  for(i = 0; i < M; i++)
    p += String.fromCharCode(
         zp + Math.floor(
         Math.random() *
         (zk - zp + 1)));

  // wypisujemy wzorzec
  // i łańcuch
  t = "<pre>" + p + "<br/>" +
      s + "<br/><span style=" +
      "'color:red'>";
 
  // 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)
      {
        t += " ";
        pp++;
      }
      t += "^";
      pp++;
    }
    i++;
    if(i > N - M) break;
    Hs = (Hs - (
         s.charCodeAt(i - 1) - 
         65) * 27) * 3 +
         s.charCodeAt(i + M - 1) - 65;
  }
  t += "</span></pre>";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>