Поиск в строках, массивах, последовательностях:
Общие подпоследовательности, дистанция.

Даны две последовательности x[1..n] и y[1..k] целых чисел. Выяснить, является ли вто- рая последовательность подпоследовательностью первой, т. е. мож- но ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка n+k.

(1 вариант) Будем сводить задачу к задаче меньшего размера.

  n1:=n;
  k1:=k;
  {инвариант:  искомый ответ <=> возможность из x[1]..x[n1] по-
   лучить y[1]..y[k1] }
  while (n1 > 0) and (k1 > 0) do begin
  | if x[n1] = y[k1] then begin
  | | n1 := n1 - 1;
  | | k1 := k1 - 1;
  | end else begin
  | | n1 := n1 - 1;
  | end;
  end;
  {n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1 <>  0
   (и n1 = 0), то ответ - нет}
  answer := (k1 = 0);

Мы использовали то, что если x[n1] = y[k1] и y[1]..y[k1] - подпоследовательность x[1]..x[n1], то y[1]..y[k1-1] - подпосле- довательность x[1]..x[n1-1].

(2 вариант) Функция x[1]..x[n1] |-< (максимальное k1, для которого y[1]..y[k1] есть подпоследовательность x[1]..x[n1]) ин- дуктивна.

Вверх по странице, к оглавлению и навигации.