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

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

Формат ввода

В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

Формат вывода

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

Пример 1:

Ввод:

3

1 2 3

3

2 3 1

Вывод:

2 3

Пример 2:

Ввод:

3

1 2 3

3

3 2 1

Вывод:

1

Разбор

PythonВыделить код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))
F = [[0]  (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if A[i - 1] == B[j - 1]:
            F[i][j] = F[i - 1][j - 1] + 1 
        else: 
            F[i][j] = max(F[i - 1][j], F[i][j - 1]) 
print(F[n][m])
 
Ans = []
i = n
j = m
while i > 0 and j > 0:
    if A[i - 1] == B[j - 1]:
        Ans.append(A[i - 1])
        i -= 1
        j -= 1
    elif F[i - 1][j] == F[i][j]:
        i -= 1 
    else: 
        j -= 1 
Ans = Ans[::-1]
 
print(Ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

const {readFileSync, writeFileSync} = require("fs");
const lines = readFileSync("input.txt", "utf8").toString().trim().split('n');
 
function test(lines) {
    const N = Number(lines[0]);
    const A = lines[1].split(' ').map(Number);
    const M = Number(lines[2]);
    const B = lines[3].split(' ').map(Number);
    const F = Array.from({length: N + 1}, () => Array.from({length: M + 1}, () => 0));
 
    for (let i = 1; i <= N; i++) {
        for (let j = 1; j <= M; j++) {
            if (A[i - 1] === B[j - 1]) {
                F[i][j] = F[i - 1][j - 1] + 1;
            } else {
                F[i][j] = Math.max(F[i - 1][j], F[i][j - 1]);
            }
        }
    }
 
    const Ans = [];
 
    let i = N;
    let j = M;
    while (i > 0 && j > 0) {
        if (A[i - 1] === B[j - 1]) {
            Ans.push(A[i - 1]);
            i -= 1;
            j -= 1;
        } else if (F[i - 1][j] === F[i][j]) {
            i -= 1;
        } else {
            j -= 1;
        }
    }
    return Ans.reverse().join(' ');
}
 
writeFileSync("output.txt", test(lines));