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

program prg;

uses Math;

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

var
  s, p : ansistring;
  Last : array [0..zk-zp] of integer;
  i, j, pp : 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);

  // dla wzorca obliczamy tablicę Last
  for i := 0 to zk-zp do
    Last[i] := 0;
  for i := 1 to M do
    Last[ord(p[i])-zp] := i;

  // szukamy pozycji wzorca w łańcuchu
  pp := 1; i := 1;
  while i <= N-M+1 do
  begin
    j := M;
    while(j > 0) and (p[j]+s[i+j-1]) do
      dec(j);
    if j = 0 then
    begin
      while pp < i do
      begin
        write (' '); inc(pp);
      end;
      write ('^'); inc(pp);
      inc(i);
    end
    else
      inc(i, max(1, j-Last[ord(s[i+j-1])-zp]));
  end;
  writeln;
end.

// Wyszukiwanie wzorca algorytmem BM
// Data:  6.06.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  =  5; // długość wzorca p
const int zp = 65; // kod pierwszego znaku
const int zk = 66; // kod ostatniego znaku

int main()
{
  string s, p;
  int Last[zk-zp+1], i, j, pp;

  srand(time(NULL));

  // generujemy łańcuch s
  s = "";
  for(i = 0; i < N; i++)
    s += zp+rand() % (zk-zp+1);

  // generujemy wzorzec
  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 tablicę Last
  for(i = 0; i <= zk-zp; i++)
    Last [i] = -1;
  for(i = 0; i < M; i++)
    Last [p[i]-zp] = i;

  // szukamy pozycji wzorca w łańcuchu
  pp = i = 0;
  while(i <= N-M)
  {
    j = M-1;
    while((j > -1) && (p[j] == s[i+j]))
      j--;
    if(j == -1)
    {
      while(pp < i)
      {
        cout << " "; pp++;
      }
      cout << "^"; pp++;
      i++;
    }
    else
      i += max(1, j-Last[s[i+j]-zp]);
  }
  cout << endl << endl;
  return 0;
}

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

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

' Funkcja wyznacza większą z dwóch liczb
'---------------------------------------
Function max (Byval a As Integer, _
              Byval b As Integer) _
              As Integer
  If a > b Then max = a Else max = b
End Function

Dim As String s, p
Dim As Integer Last(zk-zp), i, j, pp

Randomize

' generujemy łańcuch s
s = ""
For i = 1 To N
  s += Chr(zp+Cint(Rnd*(zk-zp)))
Next

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

' wypisujemy wzorzec
Print p

' wypisujemy łańcuch
Print s

' obliczamy tablicę Last []
For i = 0 To zk-zp
  Last(i) = 0
Next
For i = 1 To M
  Last(Asc(Mid(p, i, 1))-zp) = i
Next

' szukamy pozycji wzorca w łańcuchu
pp = 1: i = 1
While i <= N-M = 1
  j = M
  While(j > 0) And (Mid(p, j, 1) = Mid(s, i+j-1, 1))
    j -= 1
  Wend
  If j = 0 Then
    While pp < i
      Print " ";: pp += 1
    Wend
    Print "^";: pp += 1
    i += 1
  Else
    i += max(1, j-Last(Asc(Mid(s, i+j-1, 1))-zp))
  End If
Wend
Print
End

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

import random

N = 79  # długość łańcucha s
M =  5  # długość wzorca p
ZP = 65 # kod pierwszego znaku
ZK = 66 # kod ostatniego znaku

# generujemy łańcuch s
s = ""
for i in range(N):
    s += chr(random.randrange(ZP, ZK+1))
# generujemy wzorzec
p = ""
for i in range(M):
    p += chr(random.randrange(ZP, ZK+1))
# wypisujemy wzorzec
print(p)
# wypisujemy łańcuch
print(s)
# obliczamy tablicę t_last
t_last = [0] * (ZK-ZP+1)
for i in range(M):
    t_last[ord(p[i])-ZP] = i
# szukamy pozycji wzorca w łańcuchu
pp = 0
i = 0
while i <= N-M:
    j = M-1
    while(j > -1) and (p[j] == s[i+j]):
        j -= 1
    if j == -1:
        while pp < i:
            print(" ", end="")
            pp += 1
        print("^", end="")
        pp += 1
        i += 1
    else:
        i += max(1, j-t_last[ord(s[i+j])-ZP])
print()
print()