program BoyerMoore (input, output);
{Boyer-Moore substring match as presented in Baase}
  type
    alphabetArray = array[char] of integer;
    indexArray = array[1..2048] of integer;
    str = record
        length: integer;
        st: array[1..2048] of char
      end;

  var
    i: integer;
    p: str;
    charJump: alphabetArray;
    matchJump: indexArray;

  procedure computeJumps (p: str; var charJump: alphabetArray);
    var
      ch: char;
      k: integer;

  begin
    writeln('computeJumps');
    for ch := chr(-128) to chr(127) do
      charJump[ch] := p.length;
    for k := 1 to p.length do
      charJump[p.st[k]] := p.length - k;
  end;

  procedure computeMatchJumps (p: str; var matchJump: indexArray);
    var
      i, k, q, qq: integer;
      back: indexArray;

  begin
    writeln('computeMatchJumps');
    writeln('loop 1');
    for k := 1 to p.length do
      matchJump[k] := 2 * p.length - k;

    writeln('loop 2');
    k := p.length;
    q := p.length + 1;
    while k > 0 do
      begin
        back[k] := q;

        while (q <= p.length) and (p.st[k] <> p.st[q]) do
          begin
            if (p.length - k) < matchJump[q] then
              begin
                matchJump[q] := p.length - k;
                writeln('change matchJump ', q, ' to ', p.length - k)
              end;
            q := back[q];
          end;

        k := k - 1;
        q := q - 1
      end;

    writeln('loop 3');
    for k := 1 to q do
      if (p.length + q - k) < matchJump[k] then
        begin
          matchJump[k] := p.length + q - k;
          writeln('change matchJump ', k, ' to ', p.length + q - k)
        end;

    writeln('loop 4');
    qq := back[q];
    while q <= p.length do
      begin
        while q <= qq do
          begin
            if (p.length + qq - q) < matchJump[q] then
              begin
                matchJump[q] := p.length + qq - q;
                writeln('change matchJump ', q, ' to ', p.length + qq - q)
              end;
            q := q + 1
          end;
        qq := back[qq];
      end;

    writeln('sub ', ' pattern ', ' matchJump ', ' back ', ' patternSlide ');
    for i := 1 to p.length do
      begin
        write(i : 2, ' ', p.st[i] : 8, ' ', matchJump[i] : 10, ' ', back[i] : 4, ' ');
        writeln(i + matchJump[i] - p.length)
      end
  end;

begin
  writeln('enter string length');
  readln(p.length);
  writeln('enter string');
  for i := 1 to p.length do
    read(p.st[i]);
  computeJumps(p, charJump);

  computeMatchJumps(p, matchJump);
end.