Сама общая подпоследовательность

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

В первой строке первая строка, во второй — вторая. Каждая из строчных латинских букв, длина от $1$ до $1500$.

Строка-ответ или пустая строка, если общих символов нет.

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