|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Arthur Vartanov 2:5020/400 07 Dec 2001 22:06:37 To : Andrey Maximenko Subject : Re: Гоpодская олимпиада по инфоpматике --------------------------------------------------------------------------------
Hello, Andrey!
You wrote to Kartohin Ruslan on Fri, 7 Dec 2001 10:18:01 +0000 (UTC):
>> 4. (А это на закуску (Есть небольшие подводные камни)) Дано два файла
>> содеpжащих стpоки длиной не более 255 символов. Вывести в тpетий файл
>> все
AM> те
>> стpоки, котоpые встpечаются в обоих файлах.
>> Пpимеp:
>> 1-й файл 2-й файл Выходной файл program
>> program program define procedure
>> procedure procedure Define program
AM> Если можно использовать все алгоритмы, любые и разные, то, используя
AM> Делфи или один из других современных языков:
AM> 1. вгоняем один из файлов полностью в строку, спереди и сзади на
AM> всяк случай добавляем #13#10.
AM> 2. Каждое слово второго файла, ограниченное #13#10, проверяем на
AM> входимость в эту строку
AM> 3. Все, но ничего оригинального
Это сильно. Твой алгоритм будет иметь приемлемую скорость для небольших
файлов. А если в файле с десяток тысяч строк? Поэтому делаем так: по более
длинному файлу строим хеш-таблицу, упорядочиваем ее по возрастанию/убыванию
хэша и делаем бинарный поиск, используя хеши строк второго файла.
Естественно, учитываем коллизии.
Sincerely,
Arthur (arvar@penza.net)
PS. Как то раз пришлось решать подобную задача в реальной программе. Там
один из файлов содержал около сотни тысяч строк, другой - несколько тысяч.
Алгоритм тупого стравнения строк работал около 10 мин, а с хешированием -
всего несколько секунд.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/39513be3c236.html, оценка из 5, голосов 10
|