program PesquisaCadeias;
const
  MAXTAMTEXTO  = 1000;
  MAXTAMPADRAO = 10;
  MAXCHAR      = 256;
  NUMMAXERROS  = 10;
type
  TipoTexto = array[1..MAXTAMTEXTO] of char;
  TipoPadrao= array[1..MAXTAMPADRAO] of char;
var
  T: TipoTexto;
  P: TipoPadrao;
  n: integer;
  m: integer;
  k: integer;
  i: integer;

procedure ForcaBruta (var T: TipoTexto; n: integer; 
                      var P: TipoPadrao; m: integer);
{-- Pesquisa P[1..m] em T[1..n] --}
var i, j, k: Integer;
begin
  for i := 1 to n - m + 1 do
    begin
    k := i;  j:= 1;
    while (T[k] = P[j]) and (j <= m) do
      begin j := j + 1;  k := k + 1; end;
    if j > m then writeln (' Casamento na posicao', i:3);
    end;
end; { ForcaBruta }

procedure BMH (var T: TipoTexto; n: integer;
               var P: TipoPadrao; m: integer);
var i, j, k: Integer;
    d: array[0..MAXCHAR] of integer;
begin
  {-- Pre-processamento do padrao --}
  for j := 0 to MAXCHAR do d[j] := m;
  for j := 1 to m - 1 do d[ord(P[j])] := m - j;
  i := m;
  while i <= n do {-- Pesquisa --}
    begin
    k := i;  j := m;
    while (j>0) and (T[k] = P[j]) do 
      begin 
      k := k - 1;  j := j - 1; 
      end;
    if j = 0 then writeln(' Casamento na posicao: ', k + 1:3);
    i := i + d[ord(T[i])];
    end;
end; { BMH }

procedure BMHS (var T: TipoTexto; n: integer;
                var P: TipoPadrao; m: integer);
var i, j, k: Integer;
    d: array[0..MAXCHAR] of integer;
begin
  {-- Pre-processamento do padrao --}
  for j := 0 to MAXCHAR do d[j] := m + 1;
  for j := 1 to m do d[ord(P[j])] := m + 1 - j;
  i := m;
  while i <= n do {-- Pesquisa --}
    begin
    k := i;  j := m;
    while (j>0) and (T[k] = P[j]) do 
      begin 
      k := k - 1; j := j - 1; 
      end;
    if j = 0 then writeln(' Casamento na posicao: ', k + 1:3);
    i := i + d[ord(T[i+1])];
    end;
end; { BMHS }

procedure ShiftAndExato (var T: TipoTexto; n: Integer; 
                         var P: TipoPadrao; m: Integer);
var Masc: array[0..MAXCHAR - 1] of Integer;
    i, R:  Integer;
begin
  R := 0;
  { Pre-processamento padrao }
  for i := 0 to MAXCHAR - 1 do Masc[i] := 0;
  for i := 1 to  m do
    Masc[ord(P[i]) + 127] := Masc[ord(P[i]) + 127] or (1 shl (m - i));
  { Pesquisa }
  for i := 0 to n - 1 do
    begin
    R := ((R shr 1) or (1 shl (m - 1))) and Masc[ord(T[i + 1]) + 127];
    if (R and 1) <> 0 
    then writeln( ' Casamento na posicao ', i - m + 2 );
    end;
end; { ShiftAndExato }   

procedure ShiftAndAproximado (var T: TipoTexto; n: Integer;
                              var P: TipoPadrao; m, k: Integer);
var
  Masc: array[0..MAXCHAR - 1] of Integer;
  i, j, Ri, Rant, Rnovo:  Integer;
  R: array[0..NUMMAXERROS] of Integer;
begin
  { Pre-processamento padrao }
  for i := 0 to MAXCHAR - 1 do Masc[i] := 0;
  for i := 1 to  m do
    Masc[ord(P[i]) + 127] := Masc[ord(P[i]) + 127] or (1 shl (m - i));
  { Pesquisa }
  R[0] := 0;  Ri := 1 shl (m - 1);
  for j := 1 to k do R[j] := (1 shl (m -j)) or R[j - 1];  
  for i := 0 to n - 1 do 
    begin
    Rant := R[0];
    Rnovo := ((Rant shr 1) or Ri) and Masc[ord(T[i + 1]) + 127];
    R[0] := Rnovo;
    for j := 1 to k do 
      begin
      Rnovo := ((R[j] shr 1) and Masc[ord(T[i + 1]) + 127]) or 
                Rant or ((Rant or Rnovo) shr 1);
      Rant := R[j];
      R[j] := Rnovo or Ri;
      end;
    if (Rnovo and 1) <> 0 
    then writeln ( ' Casamento na posicao ', i + 1 );
    end;
end; { ShiftAndAproximado }

begin
  write (' Tamanho do texto: '); readln (n);
  write (' Tamanho do padrao: '); readln (m);
  write (' Texto: ');
  for i:= 1 to n do read (T[i]);  readln;
  write (' Padrao: ');
  for i := 1 to m do read (P[i]);  readln;
  writeln ('Forca bruta:');
  ForcaBruta (T, n, P, m);
  readln;
  writeln ('BMH:');
  BMH (T, n, P, m);
  readln;
  writeln ('BMHS:');
  BMHS (T, n, P, m);
  readln;
  writeln ('Shift-And-Exato:');
  ShiftAndExato (T, n, P, m);
  readln;
  writeln ('Shift-And-Aproximado:');
  write  ("Numero de erros: ");
  readln (k);
  ShiftAndAproximado (T, n, P, m, k);   
end.