Chương trình C++ in chuỗi con chung dài nhất

In chuỗi con chung dài nhất (longest common substring) của hai chuỗi A và B. Ví dụ "HelloWorld" và "world book" → "world".

Dùng quy hoạch động: bảng longest[m+1][n+1]. Nếu X[i-1]==Y[j-1] thì longest[i][j] = longest[i-1][j-1]+1. Theo dõi độ dài max và vị trí. Truy vết ngược để lấy chuỗi.

Ví dụ mã nguồn

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;

void print_lstring(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;
        }
    }
    if (len == 0) {
        cout << "There exists no common substring";
        return;
    }
    char* final_str = (char*)malloc((len + 1) * sizeof(char));
    while (longest[row][col] != 0) {
        final_str[--len] = X[row - 1];
        row--;
        col--;
    }
    cout << final_str;
}

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

Kết quả đầu ra

world