Chương trình tìm độ dài chuỗi con chung dài nhất trong C++

Giả sử chúng ta có hai chuỗi chữ thường X và Y, ta cần tìm độ dài của chuỗi con chung dài nhất giữa chúng.

Ví dụ, nếu đầu vào là X = "helloworld", Y = "worldbook", thì đầu ra sẽ là 5, vì "world" là chuỗi con chung dài nhất và độ dài của nó là 5.

Thuật toán

Để giải quyết bài toán này, ta thực hiện các bước sau:

• Định nghĩa mảng longest kích thước (m+1) x (n+1), trong đó m và n lần lượt là độ dài của X và Y.
• Khởi tạo biến len = 0 để lưu độ dài lớn nhất tìm được.
• Duyệt qua tất cả các cặp chỉ số (i, j) với i từ 0 đến m, j từ 0 đến n:
  • Nếu i == 0 hoặc j == 0: gán longest[i][j] = 0.
  • Ngược lại, nếu X[i-1] == Y[j-1]: gán longest[i][j] = longest[i-1][j-1] + 1. Cập nhật len nếu giá trị mới lớn hơn, đồng thời lưu vị trí row = i, col = j.
  • Nếu X[i-1] != Y[j-1]: gán longest[i][j] = 0.
• Trả về len.

Ví dụ triển khai (C++)

#include <iostream>
#include <cstring>
using namespace std;

int solve(char* X, char* Y, int m, int n) {
    int longest[m + 1][n + 1];
    int len = 0;
    int row, col;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                longest[i][j] = 0;
            else if (X[i - 1] == Y[j - 1]) {
                longest[i][j] = longest[i - 1][j - 1] + 1;
                if (len < longest[i][j]) {
                    len = longest[i][j];
                    row = i;
                    col = j;
                }
            } else
                longest[i][j] = 0;
        }
    }
    return len;
}

int main() {
    char X[] = "helloworld";
    char Y[] = "worldbook";
    int m = strlen(X);
    int n = strlen(Y);
    cout << solve(X, Y, m, n);
    return 0;
}

Đầu vào

"helloworld", "worldbook"

Đầu ra

5