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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
КристинаЛ
Сообщений: n/a
#1

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

08.02.2013, 11:49. Просмотров 1650. Ответов 4
Метки нет (Все метки)

Здравствуйте форумчане!! Помогите заблудшей душе....
Есть задачка , максимально быстрым способом найти наибольшую общую подстроку во множестве строк.Строк всегда больше двух . Только именно подстроку а не последовательность.
Строки состоят из маленьких латинских букв .
Например :
строка
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++
Реализация алгоритма RLE C++
Реализация алгоритма FOREL C++
C++ Реализация алгоритма
C++ Реализация алгоритма Дейкстры
Реализация алгоритма Прима C++
C++ Реализация волнового алгоритма
Реализация циклического алгоритма C++
Реализация Алгоритма Грэхема на С++ C++
C++ Реализация алгоритма DBSCAN

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Герц
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 алгоритма на с++
Ответ Создать тему
Опции темы

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