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

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

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

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

08.02.2013, 11:49. Просмотров 1746. Ответов 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++
помогите пожалуйсто написать программу: 1. Реализовать алгоритм Insertion-Sort (сортировка вставками) и Merge-Sort (сортировка слиянием)...

Реализация алгоритма - C++
Смотрите, есть функция для рисования сегмента круга: pieslice(int x, int y, int start, int end, int radius) - int start и int ende угол...

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

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

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

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

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

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

Реализация алгоритма DBSCAN - C++
Всем добрый день/ночь! Есть такой алгоритм кластеризации DBSCAN Я его реализовал на c++/qt Хотелось бы узнать у...

Реализация алгоритма Йена на С++ - C++
помогите пожалуста реализовать алгоритм Йена есть алгоритм Дейкстры нужно его доделать до Йена#include<iostream> #include<string.h> ...

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

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

Реализация циклического алгоритма - C++
Помогите пожалуйста! Мне нужно написать несколько программ, но получается не всё. Может кого заинтересует одно из заданий. Заранее огромное...


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

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

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