โปรแกรม C++ พิมพ์สตริงย่อยร่วมที่ยาวที่สุด (Longest Common Substring)

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมพิมพ์สตริงย่อยร่วมที่ยาวที่สุด

สำหรับนี้เราจะได้รับสตริงสองสตริง คือ A และ B เราต้องพิมพ์สตริงย่อยร่วมที่ยาวที่สุดของสตริงอินพุต A และ B ทั้งสอง

ตัวอย่าง ถ้าเราได้รับ "HelloWorld" และ "world book" สตริงย่อยร่วมที่ยาวที่สุดในกรณีนี้จะเป็น "world"

ตัวอย่าง

#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; 
}

ผลลัพธ์

world