|
Поиск в строках, массивах, последовательностях:
Общие подпоследовательности, дистанция.
Нахождение общих элементов двух массивов.
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; вторая добавлена для симметрии.
![](../gif/3arrow1.gif) Вверх по странице, к оглавлению и навигации.
| |