[Алгоритм, C++] Наибольшая общая правильная скобочная подпоследовательность

[Карл Кремень]

Здравствуйте!

Такая вот задача: даны две строки, только из круглых скобок, длины n <= 700.
Требуется найти правильную скобочную последовательность наибольшей длины, которая в то же время является подпоследовательностью этих двух строк. Если таких несколько, можно вывести любую.
Пример:

Input: 
())(()()()
)(())(())

Output:
(())()

Буду благодарен за идею!

[evg_m]

найти правильную

значит она начинается с ( и соблюдаются еще некоторые правила (количество и порядок).

длины n <= 700.

ну не так много, можно составить ДВА списка(для КАЖДОЙ нашей последовательности) ПРАВИЛЬНЫХ подпоследовательностей (начало + длина)
а потом эти списки СРАВНИТЬ( сравнить последовательности ВХОДЯЩИЕ в эти списки).

а можно просто
перебрать ВСЕ правильные подпоследовательности в одной из ...
и ПРОСТО проверить ЕСТЬ ЛИ такая в другой из ...
если ЕСТЬ, то сравнить с "ранее" найденной и "оставить" лучшую.

[Serge_Bliznykov]

Сообщение от Карл Кремень

Пример:

Input: 
())(()()()
)(())(())

Output:
(())()

простите, может быть, я не понял задачу, но где указанный Output в первой или во второй строчках?!

[Карл Кремень]

Сообщение от evg_m

з
перебрать ВСЕ правильные подпоследовательности в одной из ...

Так их же может быть до хрена, разве нет?

[Plague]

k=0
если "(" то k=k+1
если ")" то k=k-1

а если в ходе подсчета получим отрицательное число?
если скобочная последовательность правильная чему равно k?

[Карл Кремень]

Прошу прощения, в условии была опечатка. Требуется найти подпоследовательность, а не подстроку

[Аватар]

Может что-то не понял. Не вижу результат ни в одной из входящих строк. По идее в данном случае должно быть (). Не?

[Карл Кремень]

Прошу прощения, в условии была опечатка. Требуется найти подпоследовательность, а не подстроку

[Аватар]

Input:
())(()()()
)(())(())

Output:
(())()

Непонятки. Выделенное красным правильные подпоследовательности?

[Serge_Bliznykov]

Сообщение от Карл Кремень

Прошу прощения, в условии была опечатка. Требуется найти подпоследовательность, а не подстроку

а что такое "подпоследовательность" в вашем задании?

где найденная "подпоследовательность" (см. Output) есть в первой и во второй строчках?!

update
уже увидел пример Аватар'а.
если это верно, то задача весьма занимательна!