#include <iostream>

using namespace std;

const int N = 70;  // długość łańcucha c1
const int M =  3;  // długość łańcucha c2 - wzorzec

main()
{
  char c1[N+1], c2[M+1];
  int i,b,p,pi[M+1];

  srand((unsigned)time(NULL));

// Generujemy łańcuch do przeszukania

  for(i = 0; i < N; i++) c1[i] = 65 + rand() % 4;
  c1[N] = '\';
  
// Generujemy wzorzec

  for(i = 0; i < M; i++) c2[i] = 65 + rand() % 4;
  c2[M] = '\';

// Wyświetlamy dane wejściowe:

  cout << "s2 = " << c2 << "\n\ns1 = " << c1 << "\n     ";

// Obliczamy tablicę pi[]

  pi[0] = b = -1;
  for(i = 0; i < M; i++)
  {
    while((b > -1) && (c2[b] != c2[i])) b = pi[b];
    pi[i+1] = ++b;
  }

// Szukamy pozycji wzorca algorytmem MP

  b = 0; p = -1;
  for(i = 0; i <= N - 1; i++)
  {
    while((b > -1) && (c2[b] != c1[i])) b = pi[b];
    if(++b < M) continue;
    p = i - b + 1; break;
  }
  
// Jeśli znaleziono wzorzec w łańcuchu, wyświetlamy go
  
  if(p >= 0)
  {
    for(i = 0; i < p; i++) cout << " ";
    cout << c2;
  }
  else cout << "Wzorzec nie znaleziony.";
  cout << endl << endl;
  system("pause");
}