Главная страница


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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Интересная задача   Stepan Kuznetsov   13 Apr 2002 23:46:59 
 Re: Интересная задача   Sergey Politov   14 Apr 2002 04:50:15 
 Re: Интересная задача   Stepan Kuznetsov   14 Apr 2002 18:06:02 
 Re^2: Интересная задача   Sergey Politov   15 Apr 2002 04:22:40 
 Интересная задача   Anton Kuznetsov   15 Apr 2002 21:59:00 
 Re: Интересная задача   Sergey Politov   17 Apr 2002 04:25:31 
 Re: Интересная задача   Stepan Kuznetsov   17 Apr 2002 23:55:52 
 Интересная задача   Anton Kuznetsov   18 Apr 2002 21:32:00 
 Re^2: Интересная задача   Sergey Politov   18 Apr 2002 04:26:04 
Архивное /ru.algorithms/39915fba0d85.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional