Задачи
Наибольшая общая подпоследовательность
Наибольшая общая подпоследовательность
Даны две последовательности. Найдите длину их наибольшей общей подпоследовательности. Подпоследовательность - это последовательность, полученная из другой последовательности удалением некоторых элементов без изменения порядка следования оставшихся элементов.
Входные данные
В первой строке задана длина n\:(1 \le n \le 1000) первой последовательности. Во второй строке записаны члены первой последовательности — целые числа, не превосходящие по модулю 10^4. В третьей строке задана длина второй последовательности m\:(1 \le m \le 1000). В четвертой строке записаны члены второй последовательности — целые числа, не превосходящие по модулю 10^4.
Выходные данные
Вывести длину наибольшей общей подпоследовательности, или 0 если такой не существует.
Пример
Входные данные #1
3 1 2 3 4 2 1 3 5
Выходные данные #1
2
Входные данные #3
3 1 2 3 3 1001 1002 1003
Выходные данные #3
0