Khoảng cách chỉnh sửa (Edit Distance)

Có hai chuỗi được cho. Chuỗi đầu tiên là chuỗi nguồn và chuỗi thứ hai là chuỗi đích. Trong chương trình này, ta phải tìm cần bao nhiêu phép chỉnh sửa có thể để chuyển chuỗi thứ nhất thành chuỗi thứ hai.

Phép chỉnh sửa chuỗi có thể là: chèn một số phần tử, xóa một cái gì đó từ chuỗi đầu tiên hoặc sửa đổi một cái gì đó để chuyển thành chuỗi thứ hai.

Đầu vào và Đầu ra

Đầu vào: Hai chuỗi để so sánh.
chuỗi 1: Programming
chuỗi 2: Programs
Đầu ra: Enter the initial string: Programming
Enter the final string: Programs
Số lần thay đổi cần thiết để chuyển Programming thành Programs là 4

Thuật toán

editCount(initStr, finalStr, initLen, finalLen)
Đầu vào: Chuỗi ban đầu và chuỗi cuối cùng và độ dài của chúng.
Đầu ra: Số lần chỉnh sửa cần thiết để biến initStr thành finalStr.
Bắt đầu
  nếu initLen = 0 thì
    trả về finalLen
  nếu finalLen = 0 thì
    trả về initLen
  nếu initStr[initLen - 1] = finalStr[finalLen - 1] thì
    trả về editCount(initStr, finalStr, initLen - 1, finalLen - 1)
  answer := 1 + min của (editCount(initStr, finalStr, initLen, finalLen - 1)),
    (editCount(initStr, finalStr, initLen - 1, finalLen),
    (editCount(initStr, finalStr, initLen - 1, finalLen - 1)
  trả về answer
Kết thúc

Ví dụ (C++)

#include <iostream>
using namespace std;

int min(int x, int y, int z) {
  // tìm nhỏ nhất trong ba số
  if(x < y) {
    if(x < z)
      return x;
    else
      return z;
  } else {
    if(y < z)
      return y;
    else
      return z;
  }
}

int editCount(string initStr, string finalStr, int initLen, int finalLen) {
  if (initLen == 0)
    // khi chuỗi ban đầu rỗng, thêm tất cả ký tự của chuỗi cuối
    return finalLen;
  if (finalLen == 0)
    // khi chuỗi cuối rỗng, xóa tất cả ký tự từ chuỗi ban đầu
    return initLen;
  // khi ký tự cuối khớp, đệ quy kiểm tra ký tự trước
  if (initStr[initLen-1] == finalStr[finalLen-1])
    return editCount(initStr, finalStr, initLen-1, finalLen-1);
  // nếu ký tự cuối không khớp, kiểm tra đệ quy cho chèn, xóa và cập nhật
  return 1 + min(
    editCount(initStr, finalStr, initLen, finalLen-1),   // chèn
    editCount(initStr, finalStr, initLen-1, finalLen),   // xóa
    editCount(initStr, finalStr, initLen-1, finalLen-1)  // cập nhật
  );
}

int main() {
  string initStr;
  string finalStr;
  cout << "Enter the initial string: "; cin >> initStr;
  cout << "Enter the final string: "; cin >> finalStr;
  cout << "The number of changes required to convert " << initStr << " to " << finalStr;
  cout << " is " << editCount(initStr, finalStr, initStr.size(), finalStr.size()) << endl;
}

Đầu ra

Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4