ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Valentin Kononov                     2:5035/38.9    27 Nov 2001  02:21:24
 To : Alexander Chelmodeev
 Subject : Задача
 -------------------------------------------------------------------------------- 
 

 Пят Hоя 23 2001 22:03, Alexander wrote to Lebedev Viktor:
 
  LV>>   Имеется задача со следующим условием.
  LV>> Два относительно небольших файла. Hеобходимо их сравнить и
  LV>> обнаружить наиболее длинную цепочку совпадающих символов.
  LV>> Хотелось бы услышать ваше мнение, многоуважаемый All, как это
  LV>> сделать наиболее красиво...
  AC>
  AC>      Красиво - вряд ли, но можно попробовать в лоб. Почти методом
  AC> деления пополам.
 
     Почти красиво. Только зачем все это? Действительно в лоб, сравнивая по
 байту, ответ получим гораздо быстрее. В твоем варианте около N*2^(2*N-1)
 сравнений (длинных строк), а если сравнивать побайтно, то не более
 2^(2*N+1) сравнений единичных байтов (считая длину каждого файла 2^N)
     Алгоритм примитивный. Берем (больший) файл и с каждым байтом пробегаем
 по меньшему, находим там такие же байты, для каждого сравниваем следующие,
 пока не найдем различие. Как только рекордная длина превышает расстояние до
 конца большего файла, говорим: стоп. До конца меньшего тоже можно не доходить.
 
 Valentin
 
 --- GoldED/W32 3.0.1
  * Origin:  DIA --->> (-:!:-) <<--- LOG  (Kursk 2:5035/38.9)
 
 

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