и ведь не сложная-то идея, но как-то сразу в голову и не придет. и не сразу — тоже 
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Найти все вхождения 100 слов в длиииинный текст |
| Автор: imageman 28.12.2012, 10:25 |
| Дано: длинный текст не помещающийся в память (или в кэш). Нужно найти "координаты" всех вхождений 100-300 слов (разной длины). Т.е. на выходе что-то вроде: 1-е слово находится в тексте на позициях 3, 88, 900. 2-е слово не найдено. 3-е слово на позициях 1000, 1020, 1090 Тупой вариант использования find не проходит - текст длинный и слов довольно много, поэтому find жрет очень много ресурсов. Сейчас есть мысль использовать через CRC (как в rsync), но смущает то, что слова разной длины (от 1-й до 15 букв). Кто что посоветует? |
| Автор: Akina 28.12.2012, 10:45 |
| НаписАть спецприблуду для решения задачи. |
| Автор: nworm 28.12.2012, 22:03 |
| http://ru.wikipedia.org/wiki/%D0%90%D1%85%D0%BE-%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA |
| Автор: skyboy 28.12.2012, 22:12 |
| nworm, я правильно понял, что на основе словаря-списка искомых слов строится дерево? тогда сложность получается порядка N(длины текста для разбора), что очень круто и ведь не сложная-то идея, но как-то сразу в голову и не придет. и не сразу — тоже |
| Автор: nworm 28.12.2012, 22:14 | ||
Да, именно так. |
| Автор: imageman 28.12.2012, 22:22 |
| буду изучать! Спасибо! Нечто подобное мне и предлагали знатоки (составление конечного автомата), но тут написано намного лучше и (похоже) то, что мне надо. |
| Автор: Polesinskij 31.10.2013, 21:09 |
Модератор: Сообщение скрыто. |