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

program prg;

const
  N = 79;  // długość łańcucha s
  M =  5;  // długość wzorca p

var
  s, p : ansistring;
  KMPNext : array [ 0..M ] of integer;
  i, b, pp : integer;

begin
  randomize;

  // generujemy łańcuch s

  s := '';
  for i := 1 to N do s := s + chr ( 65 + random ( 2 ) );

  // generujemy wzorzec

  p := '';
  for i := 1 to M do p := p + chr ( 65 + random ( 2 ) );

  // dla wzorca obliczamy tablicę KMPNext [ ] 

  KMPNext [ 0 ] := -1;
  b := -1;
  for i := 1 to M do
  begin
    while( b > -1 ) and ( p [ b + 1 ] <> p [ i ] ) do b := KMPNext [ b ];
    inc ( b );
    if( i = M ) or ( p [ i + 1 ] <> p [ b + 1 ] ) then KMPNext [ i ] := b
    else KMPNext [ i ] := KMPNext [ b ];
  end;

  // wypisujemy wzorzec p

  writeln ( p );

  // wypisujemy łańcuch s

  writeln ( s );

  // poszukujemy pozycji wzorca w łańcuchu

  pp := 0; b := 0;
  for i := 1 to N do
  begin
    while( b > -1 ) and ( p [ b + 1 ] <> s [ i ] ) do b := KMPNext [ b ];
    inc ( b );
    if b = M then
    begin
      while pp < i - b do
      begin
        write ( ' ' ); inc ( pp );
      end;
      write ( '^' ); inc ( pp );
      b := KMPNext [ b ];
    end
  end;
  writeln;
end.

// Wyszukiwanie wzorca algorytmem KMP
// Data:  4.06.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 =  5;  // długość wzorca p

int main( )
{
  string s, p;
  int KMPNext [ M + 1 ], i, b, pp;

  srand ( ( unsigned )time ( NULL ) );

  // generujemy łańcuch s

  s = "";
  for( i = 0; i < N; i++ ) s += 65 + rand( ) % 2;

  // generujemy wzorzec

  p = "";
  for( i = 0; i < M; i++ ) p += 65 + rand( ) % 2;

  // dla wzorca obliczamy tablicę Next [ ] 

  KMPNext [ 0 ] = b = -1;
  for( i = 1; i <= M; i++ )
  {
    while( ( b > -1 ) && ( p [ b ] != p [ i - 1 ] ) ) b = KMPNext [ b ];
    ++b;
    if( ( i == M ) || ( p [ i ] != p [ b ] ) ) KMPNext [ i ] = b;
    else KMPNext [ i ] = KMPNext [ b ];
  }

  // wypisujemy wzorzec

  cout << p << endl;

  // wypisujemy łańcuch s

  cout << s << endl;

  // poszukujemy pozycji wzorca w łańcuchu

  pp = b = 0;
  for( i = 0; i < N; i++ )
  {
    while( ( b > -1 ) && ( p [ b ] != s [ i ] ) ) b = KMPNext [ b ];
    if( ++b == M )
    {
      while( pp < i - b + 1 )
      {
        cout << " "; pp++;
      }
      cout << "^"; pp++;
      b = KMPNext [ b ];
    }
  }
  cout << endl;
  return 0;
}

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

Const N = 79 ' długość łańcucha s
Const M =  5 ' długość wzorca p

Dim As String s, p
Dim As Integer KMPNext ( M ), i, b, pp

Randomize

' generujemy łańcuch s

s = ""
For i = 1 To N: s += Chr ( 65 + Cint ( Rnd ) ): Next

' generujemy wzorzec

p = ""
For i = 1 To M: p += Chr ( 65 + Cint ( Rnd ) ): Next

' dla wzorca obliczamy tablicę PI [ ] 

KMPNext ( 0 ) = -1: b = -1
For i = 1 To M
  while( b > -1 ) And ( Mid ( p, b + 1, 1 ) <> Mid ( p, i, 1 ) ): b = KMPNext ( b ): Wend
  b += 1:
  if( i = M ) Or ( Mid ( p, i + 1, 1 ) <> Mid ( p, b + 1, 1 ) ) Then
      KMPNext ( i ) = b
  Else
      KMPNext ( i ) = KMPNext ( b )
  End If
Next

' wypisujemy wzorzec p

Print p

' wypisujemy łańcuch s

Print s

' poszukujemy pozycji wzorca w łańcuchu

pp = 0: b = 0
For i = 1 To N
  while( b > -1 ) And ( Mid ( p, b + 1, 1 ) <> Mid ( s, i, 1 ) ): b = KMPNext ( b ): Wend
  b += 1
  If b = M Then
    While pp < i - b
      Print " ";: pp += 1
    Wend
    Print "^";: pp += 1
    b = KMPNext ( b )
  End If
Next
Print
End