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

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

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

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

08.02.2013, 11:49. Просмотров 1773. Ответов 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++
Смотрите, есть функция для рисования сегмента круга: pieslice(int x, int y, int start, int end, int radius) - int start и int ende угол...

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

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

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

Реализация обобщенного алгоритма - C++
Люди, помогите, пожалуйста. Нужно реализовать обобщенный алгоритм, который ищет в диапазоне источника последнюю подпоследовательность,...

Реализация Алгоритма Грэхема на С++ - C++
Доброго времени суток, пожалуйста помогите разобраться с написанием программы. Что непонятно: 1) Каким образом вводятся точки? В...

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

Реализация алгоритма RLE - C++
Есть задачка, надо реализовать две функции "закодировать" и "раскодировать" массив данных типа: char mass =...

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

Реализация волнового алгоритма - C++
Делаю игру Пакман В Игре имеются следующие классы Map.h #ifndef MAP_H #define MAP_H #include <SFML\Graphics.hpp>

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.02.2013, 17:26
Ответ Создать тему
Опции темы

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