// 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;

  // dla wzorca 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

' dla wzorca 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)

# dla wzorca obliczamy tablicę Last

Last = [0] * (zk - zp + 1)
for i in range(M):
    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-Last[ord(s[i+j])-zp])
print()
print()