Добавлено: 09.04.2007 17:42:25Как её решать?
Я её пытался решить так динамикой составлял таблицу всех подстрок потом проходил по таблице и рассматривал каждый вариант проверял на полуторность строки и находил наибольшую такую подстроку.
Но получил неверный ответ.
Zakhr Новичок
Зарегистрирован: 24.08.2006 Сообщения: 12
Добавлено: 09.04.2007 17:43:22Как её решать?
Я её пытался решить так динамикой составлял таблицу всех подстрок потом проходил по таблице и рассматривал каждый вариант проверял на полуторность строки и находил наибольшую такую подстроку.
Но получил неверный ответ.
ilia_night Новичок
Зарегистрирован: 27.02.2007 Сообщения: 16
Добавлено: 09.04.2007 18:25:32У меня есть несколько вариантов , почему оно у тебя не работет:
1)А не забыл ли ты удалить одинаковые символы?
2)Зачем проверять на полуторность, если надо было просто взять и поместить чётные символы одной строки в первый массив нечётные во второй, и аналогично со второй строкой.
3)Зайди на wikiпедию , и поищи раздел lcs , там написан классический алгоритм с динамикой.
admin Администратор
Зарегистрирован: 09.03.2006 Сообщения: 132
Добавлено: 10.04.2007 13:25:28решение разбивается на 4 подрешения, удовлетворяющие условию.
А далее - стандартный алгоритм поиска подпоследовательности максимальной длины через динамику.
(квадратная матрица и т.д.). - стандартный пример на подстроках.
Регистрация
Забыли пароль?
