Share 72. edit distance c++,

[giakiet635]

khoảng cách #Edit, #C ++, #AlGorithM, lập trình
## 72. Chỉnh sửa khoảng cách trong C ++

Khoảng cách chỉnh sửa là thước đo sự giống nhau giữa hai chuỗi.Nó được tính toán bằng cách đếm số lượng hoạt động tối thiểu cần thiết để chuyển đổi một chuỗi sang chuỗi kia.Các hoạt động được phép là chèn, xóa và thay thế một ký tự duy nhất.

Khoảng cách chỉnh sửa có thể được tính toán bằng thuật toán lập trình động.Thuật toán hoạt động bằng cách xây dựng một bảng khoảng cách, trong đó mỗi mục nhập trong bảng thể hiện khoảng cách chỉnh sửa giữa các ký tự `i` đầu tiên của chuỗi` A` và các ký tự `j` đầu tiên của chuỗi` b`.

Bảng được khởi tạo với các giá trị sau:

`` `
D [0] [0] = 0
cho i = 1 đến | a |:
d [0] = i
cho j = 1 đến | b |:
d [0] [j] = j
`` `

Các mục còn lại trong bảng được tính toán bằng cách sử dụng mối quan hệ tái phát sau:

`` `
d [j] = min (d [i-1] [j] + 1, d [j-1] + 1, d [i-1] [j-1] + (a ! = B [J])))
`` `

Khoảng cách chỉnh sửa là giá trị của `d [| a |] [| b |]`.

Sau đây là việc triển khai thuật toán khoảng cách chỉnh sửa trong C ++:

`` `C ++
#include <Istream>
#include <Vector>

sử dụng không gian tên STD;

int editdistance (chuỗi a, chuỗi b) {
int n = a.length ();
int m = b.length ();

vector <vector <int >> d (n + 1, vector <int> (m + 1));

for (int i = 0; i <= n; i ++) {
d [0] = i;
}

for (int j = 0; j <= m; j ++) {
d [0] [j] = j;
}

for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
d [j] = min (d [i - 1] [j] + 1, d [j - 1] + 1, d [i - 1] [j - 1] + (a [i- 1]! = B [J - 1]));
}
}

trả lại d [n] [m];
}

int main () {
Chuỗi A = "ABCDEF";
Chuỗi B = "Azced";

cout << editdistance (a, b) << endl;

trả lại 0;
}
`` `

## hashtags

* khoảng cách #Edit
* #C ++
* #AlGorithM
* #lập trình năng động
=======================================
#Edit distance, #C++, #AlGorithM, #Dynamic programming
## 72. Edit Distance in C++

The edit distance is a measure of the similarity between two strings. It is calculated by counting the minimum number of operations required to transform one string into the other. The operations allowed are insertion, deletion, and substitution of a single character.

The edit distance can be computed using a dynamic programming algorithm. The algorithm works by building up a table of distances, where each entry in the table represents the edit distance between the first `i` characters of string `A` and the first `j` characters of string `B`.

The table is initialized with the following values:

```
d[0][0] = 0
for i = 1 to |A|:
d[0] = i
for j = 1 to |B|:
d[0][j] = j
```

The remaining entries in the table are computed using the following recurrence relation:

```
d[j] = min(d[i-1][j] + 1, d[j-1] + 1, d[i-1][j-1] + (A != B[j]))
```

The edit distance is the value of `d[|A|][|B|]`.

The following is an implementation of the edit distance algorithm in C++:

```c++
#include <iostream>
#include <vector>

using namespace std;

int editDistance(string A, string B) {
int n = A.length();
int m = B.length();

vector<vector<int>> d(n + 1, vector<int>(m + 1));

for (int i = 0; i <= n; i++) {
d[0] = i;
}

for (int j = 0; j <= m; j++) {
d[0][j] = j;
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[j] = min(d[i - 1][j] + 1, d[j - 1] + 1, d[i - 1][j - 1] + (A[i - 1] != B[j - 1]));
}
}

return d[n][m];
}

int main() {
string A = "abcdef";
string B = "azced";

cout << editDistance(A, B) << endl;

return 0;
}
```

## Hashtags

* #Edit distance
* #C++
* #AlGorithM
* #Dynamic programming