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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.71
konstantinx2525
5 / 0 / 0
Регистрация: 07.11.2010
Сообщений: 16
#1

Найти наибольшую общую подпоследовательность двух последовательностей - C++

07.12.2010, 13:49. Просмотров 2160. Ответов 1
Метки нет (Все метки)

Задача об отыскании наибольшей общей подпоследовательности (динамическое программирование). Даны две последовательности символов (строки), необходимо найти их наибольшую общую подпоследовательности, т.е. такую последовательность символов, которая бы входила в качестве подпоследовательности в обе исходные последовательности и была бы максимальной длины. Говорят, что последовательность s является подпоследовательностью последовательности w, если s состоит из тех символов, что и w, причем порядок их записи соответствует порядку в w. Например, имеется две последовательности символов «ABCDEFG» и «BTDEKLFG», тогда их наибольшая общая подпоследовательности – «BDEFG». Данная задача решается с помощью принципов динамического программирования
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2010, 13:49     Найти наибольшую общую подпоследовательность двух последовательностей
Посмотрите здесь:

C++ Функция для сравнения двух символьных последовательностей
В заданном числе найти максимальную по длине подпоследовательность C++
Найти ее максимальную возрастающую подпоследовательность C++
C++ В двух строках найти подстроки и наибольшую подстроку
C++ Найти наибольшую по величине сумму двух соседних элементов массива
Найти произведение двух последовательностей наиболее близкое к числу R C++
C++ Найти наибольшую возрастающую подпоследовательность в массиве
Найти максимально длинную подпоследовательность чисел по условию C++
Объединение двух упорядоченных последовательностей чисел в одну C++
Из двух заданных последовательностей образовать новую согласно условию C++
C++ Найти площадь пересечения, то есть общую часть двух прямоугольников (не могу понять алгоритм решения)
В массиве найти произведение двух заданных последовательностей чисел; полученные произведения сравнить C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.12.2010, 15:41     Найти наибольшую общую подпоследовательность двух последовательностей #2
Вам просто нужно алгоритм объяснить или код написать?
И еще есть вопросы:
- символы в начальных последовательностях только заглавные английские?
- если наибольших общих подпоследовательностей несколько, то выводим любую?
Yandex
Объявления
07.12.2010, 15:41     Найти наибольшую общую подпоследовательность двух последовательностей
Ответ Создать тему
Опции темы

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