blob: 9a0469c8b74e7dbedcee948713091049b07b502a (
plain)
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#include <iostream>
#include <fstream>
using namespace std;
enum class Arrow {
Top,
Left,
TopLeft,
};
void
lcs(string x, string y, ostream& out)
{
int m = x.length()+1;
int n = y.length()+1;
int** C = new int*[m];
Arrow** B = new Arrow*[m];
int i, j;
for (i = 0; i < m; ++i) {
C[i] = new int[n];
C[i][0] = 0;
B[i] = new Arrow[n];
}
for (i = 0; i < n; ++i)
C[0][i] = 0;
for (i = 1; i < m; ++i) {
for (j = 1; j < n; ++j) {
if (x.at(i-1) == y.at(j-1)) {
C[i][j] = C[i-1][j-1]+1;
B[i][j] = Arrow::TopLeft;
} else if (C[i][j-1] >= C[i-1][j]) {
C[i][j] = C[i][j-1];
B[i][j] = Arrow::Left;
} else {
C[i][j] = C[i-1][j];
B[i][j] = Arrow::Top;
}
}
}
string r;
for (i = m-1, j = n-1; i != 0 && j != 0; ) {
if (B[i][j] == Arrow::TopLeft) {
r += x.at(i-1);
i--;
j--;
} else if (B[i][j] == Arrow::Top) {
i--;
} else {
j--;
}
}
for (i = 0; i < m; ++i) {
delete[] C[i];
delete[] B[i];
}
delete[] C;
delete[] B;
for (auto i = r.rbegin(); i != r.rend(); ++i)
out << *i;
out << endl;
}
int
main(int argc, char** argv)
{
int ts = (argc > 1) ? stoi(argv[1]) : 100;
ifstream fin("input.txt");
ofstream fout("output.txt");
for (int i = 0; i < ts; ++i) {
int n;
string s1, s2;
fin >> n >> n >> s1 >> s2;
lcs(s1, s2, fout);
}
fin.close();
fout.close();
return 0;
}
|
