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

Нахождение общих элементов двух массивов.

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

Замечание. В третьей альтернативе достаточно было бы увеличивать одну из переменных k1, l1; вторая добавлена для симметрии.

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