Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях / Общие подпоследовательности. Дистанция / Задача о наибольшей общей подпоследовательности. /
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
Введение

Для начала определим, в чем заключается задача:




Пусть у нас есть некоторый образец - короткая строка и текст - длинная.


Но, в отличие от точного поиска подстроки в строке, мы хотим знать, появляются ли буквы образца в том же порядке ( но, возможно, на разном расстоянии ) в тексте.


Если да, то образец - подпоследовательность текста.


Например:


Является ли 'nano' подпоследовательностью 'nematode knowledge' ?


Да, причем единственным образом.


Вот строка с выделенной подпоследовательностью: 'NemAtode kNOwledge'.


Псевдокод этой задачи можно записать так:



subseq(char * P, char * T)
{
while (*T != '\0')
if (*P == *T++ && *++P == '\0')
return TRUE;
return FALSE;
}




А теперь собственно наша задача.


Что, если образец не появляется в тексте ? Тогда часто бывает нужно найти самую длинную подпоследовательность, которая появляется и там и там.


Текст и образец теперь равноправны, поэтому обозначим их просто строками A и В. Длина A - m, B - n символов.



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

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь
Гороскоп на 2016 год - гороскоп на год обезьяны.