Вхождение матрицы в матрицу, Вхождение матрицы в матрицу Опции

[Xopek]

Дано задание написать программу...
Тема: дихотомический поиск в матрице на включение.
Короче надо определить включает ли матрица A в себя матрицу B.
Подскажите плиз теорию и если есть мона исходники.

[volvo]

Да простит меня Altair, но по-моему можно немного ускорить процесс поиска.
Для простоты массивы - статические...

const
  n1 = 8; m1 = 8;
  n2 = 3; m2 = 3;

  a_big: array[1 .. n1, 1 .. m1] of integer = (
    (1, 2, 3, 4, 5, 6, 7, 8),
    (6, 3, 4, 5, 6, 7, 8, 9),
    (1, 7, 2, 9, 3, 7, 3, 2),
    (6, 2, 4, 5, 6, 7, 0, 2),
    (5, 3, 3, 7, 3, 2, 5, 2),
    (1, 8, 2, 5, 1, 9, 0, 0),
    (0, 9, 2, 5, 6, 7, 2, 1),
    (2, 0, 3, 0, 6, 2, 5, 7)
  );

  a_small: array[1 .. n2, 1 .. m2] of integer = (
    (4, 5, 6),
    (5, 6, 7),
    (9, 3, 7)
  );


var
  i, j, k, l: integer;
  bad: boolean;

begin
  for i:=1 to n1 - n2+1 do begin { Зачем перебирать ВСЕ элементы строки?  }
    for j:=1 to m1 - m2+1 do begin
      if a_big[i, j] = a_small[1, 1] then begin

        bad := false;

        k := 1;
        repeat

          l := 1;
          repeat

            bad := a_big[i + k - 1, j + l - 1] <> a_small[k, l];

            inc(l);
          { Ну и здесь не идем до конца, если уже нашли неверный элемент }
          until (l > m2) or bad; 
          inc(k);
        until (k > n2) or bad;

        if not bad then writeln('found: ', i:3, j:3);
      end
    end
  end;
end.