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

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

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

  // obliczamy tablicę KMPNext
  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

' obliczamy tablicę KMPNext
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

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

import random

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

# generujemy łańcuch s
s = ""
for i in range(N):
    s += chr(random.randrange(65, 67))
# generujemy wzorzec p
p = ""
for i in range(M):
    p += chr(random.randrange(65, 67))
# obliczamy tablicę KMPNext
kmp_next = [-1]
b = -1
for i in range(1, M+1):
    while (b > -1) and (p[b] != p[i-1]):
        b = kmp_next[b]
    b += 1
    if(i == M) or (p[i] != p[b]):
        kmp_next.append(b)
    else:
        kmp_next.append(kmp_next[b])
# wypisujemy wzorzec p
print(p)
# wypisujemy łańcuch s
print(s)
# poszukujemy pozycji wzorca w łańcuchu
pp = 0
b = 0
for i in range(N):
    while (b > -1) and (p[b] != s[i]):
        b = kmp_next[b]
    b += 1
    if b == M:
        while pp < i-b+1:
            print(" ", end="")
            pp += 1
        print("^", end="")
        pp += 1
        b = kmp_next[b]
print()
print()

<html>
  <head>
    <title>
      KMP
    </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 KMP
          <br/></b>
          &nbsp;&nbsp;
          (C)2026 mgr
          Jerzy Wałaszek
          &nbsp;&nbsp;
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wyniki:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

function main()
{
  var N = 79; // długość s
  var M =  5; // długość p

  var s, p, i, b, pp, t;
  var KMPNext = new Array
                (M + 1);

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

  // generujemy wzorzec p
  p = "";
  for(i = 0; i < M; i++)
    p += String.fromCharCode(
         65 + Math.floor(
         Math.random() * 2));

  // dla wzorca obliczamy
  // tablicę PI[]
  KMPNext[0] = b = -1;
  for(i = 1; i <= M; i++)
  {
    while((b>-1) &&
          (p.charAt(b) !=
           p.charAt(i - 1)))
      b = KMPNext[b];
    ++b;
    if((i == M) ||
       (p.charAt(i) !=
        p.charAt(b)))
      KMPNext[i] = b;
    else
      KMPNext[i] = KMPNext[b];
  }

  // wypisujemy wzorzec p
  t = "<pre class='small'> " +
      p + "<br/> ";

  // wypisujemy łańcuch s
  t += s + " <br/> " +
       "<span style=" +
       "'color:red'>";
 
  // poszukujemy pozycji
  // wzorca w łańcuchu
  pp = b = 0;
  for(i = 0; i < N; i++)
  {
    while((b>-1) &&
          (p.charAt(b) !=
           s.charAt(i)))
      b = KMPNext[b];
    if(++b == M)
    {
      while(pp < i - b + 1)
      {
        t += " ";
        pp++;
      }
      t += "^";
      pp++;
      b = KMPNext[b];
    }
  }
  t += "</span></pre>";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>