ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Politov                       2:5015/176.18  18 Apr 2002  04:26:04
 To : Sergey Politov
 Subject : Re^2:  Интересная задача
 -------------------------------------------------------------------------------- 
 

 
 До меня дошли слухи, что *17.04.02* *5:25:31* пролетало сообщение
 от Sergey к *Anton Kuznetsov* про *"Re: Интересная задача"*. И я решил
 вмешаться.
 
 [...]
 
  SP> А вообще можно попробовать сделать так. Будем по одной строке строить
  SP> конечный автомат перебирая ее подстроки, а другую по нему прогонять. Если
  SP> подстроку перебирать фиксируя первый символ, а другой ища дихотомией, то
  SP> можно получить сложность O(mlogm+n).
 
 Я стормозил с подсчетом сложности. При таком подходе получается O(m(m+n)logm),
 что несколько хуже чем O(nm)
 
 np: Therion - The King
 Искренне Ваш
                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