โปรแกรมหาความยาวของสตริงย่อยร่วมที่ยาวที่สุดใน C++

สมมติว่าเรามีสตริงตัวพิมพ์เล็กสองตัวคือ X และ Y เราต้องการหาความยาวของสตริงย่อยร่วมที่ยาวที่สุดของทั้งสอง

เช่น หากอินพุตคือ X = "helloworld", Y = "worldbook" ผลลัพธ์จะเป็น 5 เนื่องจาก "world" เป็นสตริงย่อยร่วมที่ยาวที่สุดและมีความยาว 5

ขั้นตอนการแก้ปัญหา

• สร้างอาร์เรย์ longest ขนาด (m+1) x (n+1)
• กำหนด len := 0
• วนลูป i จาก 0 ถึง m:
  • วนลูป j จาก 0 ถึง n:
    • ถ้า i = 0 หรือ j = 0: longest[i][j] := 0
    • ถ้า X[i-1] = Y[j-1]: longest[i][j] := longest[i-1][j-1] + 1 และอัปเดต len, row, col หากค่ามากกว่าเดิม
    • อื่นๆ: longest[i][j] := 0
• คืนค่า len

ตัวอย่างโค้ด

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

อินพุต

"helloworld", "worldbook"

เอาต์พุต

5