Форум программистов, компьютерный форум CyberForum.ru

Реализация LCS алгоритма на с++ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
КристинаЛ
Сообщений: n/a
08.02.2013, 11:49     Реализация LCS алгоритма на с++ #1
Здравствуйте форумчане!! Помогите заблудшей душе....
Есть задачка , максимально быстрым способом найти наибольшую общую подстроку во множестве строк.Строк всегда больше двух . Только именно подстроку а не последовательность.
Строки состоят из маленьких латинских букв .
Например :
строка
C++
1
2
"abcdfg"
"hjabckld"
так вот общая подстрока abc -
C++
1
2
"ABCdfg"
"hjABCkld"
а общая последовательность abcd
C++
1
2
"ABCDfg"
"hjABCklD"
- то есть, нужна только подстрока.
Я решила найти в интернете , и нашла две красивые реализации , через "хэши" и через суффиксный автомат.
По "хэшам" я не нашла описания алгоритма ,и даже не поняла как это можно реализовать .
А вот по суффиксному автомату я нашла подробную статью ,тут http://e-maxx.ru/algo/suffix_automata , там реализован алгоритм поиска "наидлиннейшей общей подстроки двух строк" , реализован сам автомат на с++, и описан алгоритм для нескольких строк (в самом низу) , но я не могу его реализовать .
Может кто нибудь объяснить на пальцах алгоритм для нескольких строк или предложить другой более оптимальный алгоритм , например с "хэшами" ?
Буду безумно благодарна.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.02.2013, 11:49     Реализация LCS алгоритма на с++
Посмотрите здесь:

C++ Реализация алгоритма Мандельброта
Реализация алгоритма C++
C++ Реализация алгоритма кодирования Шеннона-Фано
Реализация алгоритма Йена на С++ C++
Реализация алгоритма RLE C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
08.02.2013, 13:41     Реализация LCS алгоритма на с++ #2
Алгоритм Укконена, почитай в книжке Дэна Гасфилда или на википедии.
КристинаЛ
Сообщений: n/a
08.02.2013, 14:35     Реализация LCS алгоритма на с++ #3
Цитата Сообщение от Герц Посмотреть сообщение
Алгоритм Укконена, почитай в книжке Дэна Гасфилда или на википедии.
Неееет! Алгоритм Укконена это алгоритм построения суффиксного дерева за линейное время , тут у меня проблем не возникло , а проблема в применение этого дерева.
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
08.02.2013, 17:18     Реализация LCS алгоритма на с++ #4
Если дерево построено, найти по нему наибольшую общую подстроку - тривиальная задача. Читай книгу Гасфилда.
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
08.02.2013, 17:26     Реализация LCS алгоритма на с++ #5
с хэшами - это алгоритм Рабина-Карпа что ли?
в википедии он прилично расписан...
а ещё ваша задача хорошо расписана тут : http://habrahabr.ru/post/142589/
Yandex
Объявления
08.02.2013, 17:26     Реализация LCS алгоритма на с++
Ответ Создать тему
Опции темы

Текущее время: 23:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru