Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
Inside1995
3 / 3 / 1
Регистрация: 04.04.2017
Сообщений: 48
1

Самая длинная общая подпоследовательность строк/ НОП строк (Динамическое программирование)

09.04.2017, 17:26. Просмотров 1099. Ответов 1

Доброго времени суток. Помогите пожалуйста разобраться с алгоритмом НОП строк.
Суть алгоритма. Необходимо найти самую длительную последовательность строк. Хочу обратить внимания на то, что подпоследовательность отличается от подстроки.
Например: дана строка А = "ABCD", в этой строке:
ABC можно считать подстрокой, также можно сказать что это подпоследовательность, НО например ABD является подпоследовательностью строки А, но подстрокой оно не является. Т.е. если даны две строки:
А = "ABCBDAB"
B = "BDCABA", то НОП для этих строк будет = "BCBA". После прочтения описания этого алгоритма я понял как его реализовать и как он работает, НО я так и не смог понять почему нужно все это делать. Если кто-то в состоянии объяснить на пальцах суть работы буду очень благодарен. Заранее спасибо. Если кому надо- могу скинуть реализацию.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2017, 17:26
Ответы с готовыми решениями:

Наибольшая общая подпоследовательность с восстановлением ответа
Даны две последовательности, требуется найти и вывести их наибольшую общую...

Перенос строк в StringGrid когда строка длинная
Простейшая вещь которую, казалось бы, и так понятно потребуется пользователям...

StringGrid динамическое добавление строк
Добрый день, есть программа : Выводит на экран имя файла,размер файла,дату...

StringGrid: динамическое добавление строк и назначение типа столбцов
Доброго дня! Есть ли StringGrid, которому можно было задать тип конкретной...

Программирование с использованием строк
Условие: Дана строка, состоящая из групп комбинаций нулей и единиц, например,...

1
Новичок
Модератор
1512 / 981 / 465
Регистрация: 17.07.2012
Сообщений: 4,979
Завершенные тесты: 3
11.04.2017, 19:31 2
Лучший ответ Сообщение было отмечено Inside1995 как решение

Решение

Цитата Сообщение от Inside1995 Посмотреть сообщение
Необходимо найти самую длительную последовательность строк
самую длинную общую подпоследовательность
Есть хорошее видео где объясняют алгоритм.

Если что-то непонятно, задавайте вопросы.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.04.2017, 19:31

Таблица строк - определить количество строк, TStringGrid
Как определить количество строк, не содержащих ни одного нулевого элемента в...

Динамическое программирование: самая длинная строго возрастающая подпоследовательность
Здравствуйте!!! У меня есть такое задание: дана последовательность целых чисел....

Динамическое программирование. Требуется идея для решения. Общая подпоследовательность
Заданы две строки длиной не больше 10000. Нужно найти самую хорошую...


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

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

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