Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Проверка на вхождение в качестве подпоследовательности - Программирование от RIN.RU
Проверка на вхождение в качестве подпоследовательности

(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]) индуктивна.




 8  Комментарии к статье  8  Обсудить в форуме  8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь