Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 29.01.2011, 19:51
Новичок

Отправить личное сообщение для NixonKNR Посмотреть профиль Найти все сообщения от NixonKNR
 
Регистрация: 29.01.2011
Сообщений: 4

Поиск общих подстрок, выбор алгоритма
Всем привет!
Я нашел 2 алгоритма решающих эту задачу:
1. Алгоритм Шинглов - http://www.codeisart.ru/python-shingles-algorithm/
2. Наивный алгоритм - http://ru.wikipedia.org/wiki/%D0%9D%...BE%D0%BA%D0%B0
Для полного счастья мне нужен еще один)
Замечание: Общая подпоследовательность не то же самое что общая подстрока. Общие элементы должны идти подряд.
Если кто знает, подскажите, пожалуйста. Заранее спасибо!
  #2  
Старый 30.01.2011, 05:13
гocть

 
Сообщений: n/a

через суффиксные деревья можно.
пусть s, t - строки. строишь дерево для строки s$t#, где $, # - спецсимволы, не встречающиеся в исходных строках. обходишь дерево, помечаешь в поддеревье каких вершин есть $ или #, потом выбираешь самую глубокую из вершин, содержащих и $ и #, это и есть ответ.
  #3  
Старый 30.01.2011, 18:03
Новичок

Отправить личное сообщение для NixonKNR Посмотреть профиль Найти все сообщения от NixonKNR
 
Регистрация: 29.01.2011
Сообщений: 4

спс за идею!
Суфиксные деревья - интересное предложение. Скорее всего мне подойдет. Сейчас начну изучать эту область. Правда вконце думаю будут проблемы с выделением(подчеркиванием) совпавшего текста...ну и хрен с ним)
  #4  
Старый 30.01.2011, 18:26
Новичок

Отправить личное сообщение для NixonKNR Посмотреть профиль Найти все сообщения от NixonKNR
 
Регистрация: 29.01.2011
Сообщений: 4

Сообщение от NixonKNR
Правда вконце думаю будут проблемы с выделением(подчеркиванием) совпавшего текста...ну и хрен с ним)
а не, сор. "Номер суффикса является индексом его начала в тексте"
Короче, кому надо, вот подробное и графическое описание алгоритма, предложенного человеком, который способен трезво мыслить в начале четвертого
http://yury.name/internet/01ianote.pdf 3 стр.

Последний раз редактировалось NixonKNR, 30.01.2011 в 18:48.
  #5  
Старый 31.01.2011, 17:37
Новичок

Отправить личное сообщение для cat_baxter Посмотреть профиль Найти все сообщения от cat_baxter
 
Регистрация: 16.11.2010
Сообщений: 6

Вот это не подойдет?

http://code.google.com/p/google-diff-match-patch/
  #6  
Старый 31.01.2011, 22:33
гocть

 
Сообщений: n/a

и где там решение озвученной задачи?

для diff'ов всяких вообще нужна наибольшая общая *подпоследовательность*, а не подстрока, и ТС ясно сказал, что нужна подстрока, а не наоборот.
  #7  
Старый 05.02.2011, 19:52
Новичок

Отправить личное сообщение для NixonKNR Посмотреть профиль Найти все сообщения от NixonKNR
 
Регистрация: 29.01.2011
Сообщений: 4

что значит mach и path я особо не разбирался, а вот diff, судя по "Demo diff", решает поставленную задачу. Осталось его запустить...
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск алгоритма AndreyA Графы 9 03.11.2010 12:50
поиск алгоритма RUmkO Реализация, исходники, языки 8 05.03.2009 18:33
Поиск эффективного алгоритма вращения Vacuum Обработка изображений, звук, графика 1 15.10.2008 06:44
Оптимальный выбор Gviber Реализация, исходники, языки 0 23.08.2008 13:05