Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
КристинаЛ
0 / 0 / 0
Регистрация: 05.02.2013
Сообщений: 2
#1

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

08.02.2013, 11:49. Просмотров 1951. Ответов 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 , там реализован алгоритм поиска "наидлиннейшей общей подстроки двух строк" , реализован сам автомат на с++, и описан алгоритм для нескольких строк (в самом низу) , но я не могу его реализовать .
Может кто нибудь объяснить на пальцах алгоритм для нескольких строк или предложить другой более оптимальный алгоритм , например с "хэшами" ?
Буду безумно благодарна.
http://www.cyberforum.ru/cpp-beginners/thread1030178.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.02.2013, 11:49
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Реализация LCS алгоритма на с++ (C++):

Реализация алгоритма
помогите пожалуйсто написать программу: 1. Реализовать алгоритм Insertion-Sort...

Реализация циклического алгоритма
Помогите понять как реализовать алгоритм. Допустим после пары шагов алгоритма...

Реализация алгоритма Адлемана
Ребят, помогите ,пожалуйста, найти код алгоритма Адлемана, очень надо....

Реализация алгоритма Дейкстры
Кто может подсказать (или указать где найти) код алгоритма Дейкстры на С++?

Реализация алгоритма DBSCAN
Всем добрый день/ночь! Есть такой алгоритм кластеризации DBSCAN Я его...

4
Герц
524 / 341 / 12
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
08.02.2013, 13:41 #2
Алгоритм Укконена, почитай в книжке Дэна Гасфилда или на википедии.
0
КристинаЛ
0 / 0 / 0
Регистрация: 05.02.2013
Сообщений: 2
08.02.2013, 14:35 #3
Цитата Сообщение от Герц Посмотреть сообщение
Алгоритм Укконена, почитай в книжке Дэна Гасфилда или на википедии.
Неееет! Алгоритм Укконена это алгоритм построения суффиксного дерева за линейное время , тут у меня проблем не возникло , а проблема в применение этого дерева.
0
Герц
524 / 341 / 12
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
08.02.2013, 17:18 #4
Если дерево построено, найти по нему наибольшую общую подстроку - тривиальная задача. Читай книгу Гасфилда.
0
abit
272 / 271 / 83
Регистрация: 03.02.2013
Сообщений: 770
08.02.2013, 17:26 #5
с хэшами - это алгоритм Рабина-Карпа что ли?
в википедии он прилично расписан...
а ещё ваша задача хорошо расписана тут : http://habrahabr.ru/post/142589/
0
08.02.2013, 17:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2013, 17:26
Привет! Вот еще темы с решениями:

Реализация алгоритма Мандельброта
Знаю, этим уже давно никого не удивить, но я еще раз решил почтить память Бенуа...

Реализация алгоритма Прима
Алгоритм Прима?кто может написать?

Реализация циклического алгоритма
Помогите пожалуйста! Мне нужно написать несколько программ, но получается не...

Реализация алгоритма FOREL
Не буду слишком наглым и не буду просить готовое решение, но вопросы будут на...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru