blob: a7b93610ae199d1abff6d9f985947af9dd3b35d9 (
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
|
#include <iostream>
#include <fstream>
using namespace std;
enum class Arrow {
Top,
Left,
TopLeft,
};
int
lcs(string x, string y)
{
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-1][j] >= C[i][j-1]) {
C[i][j] = C[i-1][j];
B[i][j] = Arrow::Top;
} else {
C[i][j] = C[i][j-1];
B[i][j] = Arrow::Left;
}
}
}
int r { 0 };
for (i = m-1, j = n-1; i != 0 && j != 0; ) {
if (B[i][j] == Arrow::TopLeft) {
r++;
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;
return r;
}
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;
fout << lcs(s1, s2) << endl;
}
fin.close();
fout.close();
return 0;
}
|
