blob: 90610069888f3178a5685eccff269cacd482931c (
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
|
#include <iostream>
#include <fstream>
using namespace std;
int
lev(string x, string y)
{
int m = x.length() + 1;
int n = y.length() + 1;
int i, j;
int** c = new int*[m];
for (i = 0; i < m; ++i)
c[i] = new int[n];
for (i = 0; i < m; ++i)
c[i][0] = i;
for (i = 0; i < n; ++i)
c[0][i] = i;
for (i = 1; i < m; ++i) {
for (j = 1; j < n; ++j) {
int cost = (x[i-1] != y[j-1]);
c[i][j] = min(min(c[i-1][j]+1, c[i][j-1]+1), c[i-1][j-1]+cost);
}
}
int r = c[m-1][n-1];
for (i = 0; i < m; ++i)
delete[] c[i];
delete[] c;
return r;
}
int
main(int argc, char** argv)
{
int ts = (argc > 1) ? stoi(argv[1]) : 100;
ifstream fin("input.txt");
ofstream fout("output.txt");
int n, m;
string s1, s2;
for (int i = 0; i < ts; ++i) {
fin >> n >> m >> s1 >> s2;
fout << lev(s1, s2) << endl;
}
fin.close();
fout.close();
return 0;
}
|
