|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Anton Kuznetsov 2:5030/566.13 15 Apr 2002 21:59:00 To : Sergey Politov Subject : Интересная задача --------------------------------------------------------------------------------
А 15 Апр 02 04:22 Sergey Politov написал Stepan Kuznetsov письмо, и я решил
вмешаться:
SP> //Привет Stepan, //
SP>
SP> До меня дошли слухи, что *14.04.02* *17:06:02* пролетало сообщение
SP> от Stepan к *Sergey Politov* про *"Re: Интересная задача"*. И я решил
SP> вмешаться.
SP>
SP>
SP> [...]
SP>
SP>>> А последовательность может быть pазpывна, т.е. для ababa и acaca,
SP>>> ответ какой? aaa или a?
SK>> В этом случае ответом будет "а". Hо твое пpедложение с pазpывной
SK>> последовательностью интеpесно, но тут возникает дpугой вопpос
SK>> насколько "pазpывной" она может быть.Пpимеp: пеpвый символ с начала
SK>> последовательности, остальные в конце. И как опpеделить?
SP>
SP> Вообще говоря есть известная задача. Если два упорядоченных
SP> мильтимножества надо найти максимальное упорядоченное мультимножетсво,
SP> которое бы содержалось в двух исходных. Решается динамикой. Эту задачу
SP> можно решать аналогично - т.е. за O(mn), динамически расчитывать f(i,j) -
SP> максимальная длина общей подпоследовательноси, заканчивающаяся на i-м и
SP> j-м символе соответственно, считается ну очень просто.
А может сделать так: f(i) - длина общей подпоследовательности заканчивающаяся
на i-м символе?
До свидания, Sergey!
* Origin: Ya! (2:5030/566.13)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/39343cbb1556.html, оценка из 5, голосов 10
|