|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Sergey Politov 2:5015/176.18 17 Apr 2002 04:25:31 To : Anton Kuznetsov Subject : Re: Интересная задача --------------------------------------------------------------------------------
До меня дошли слухи, что *15.04.02* *20:59:00* пролетало сообщение
от Anton к *Sergey Politov* про *"Интересная задача"*. И я решил вмешаться.
[...]
AK> А может сделать так: f(i) - длина общей подпоследовательности
AK> заканчивающаяся на i-м символе?
Hа i-м символе какой из строк? Имхо даже если ты так сможешь сделать,
то все равно сложность получится O(mn).
А вообще можно попробовать сделать так. Будем по одной строке строить
конечный автомат перебирая ее подстроки, а другую по нему прогонять.
Если подстроку перебирать фиксируя первый символ, а другой ища дихотомией,
то можно получить сложность O(mlogm+n).
np: Iced Earth - Frankenstein
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: RAP - кал, слушай металл. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/39915fba0d85.html, оценка из 5, голосов 10
|