lcs.cpp (2)

Bài toán

Cho hai xâu, tình dãy con chung dài nhất của chúng.

Độ phức tạp

O(mn)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <string.h>

int m, n;

char a[12309];

char b[12309];

int F[2309][2309];

int max(int a, int b) { return a > b ? a : b; }

int main() {

    int i, j;

    scanf("%s%s", a + 1, b + 1);

    m = strlen(a + 1);

    n = strlen(b + 1);

    for (i = 1; i <= m; i++)

        for (j = 1; j <= n; j++)

            if (a[i] == b[j])

                F[i][j] = F[i - 1][j - 1] + 1;

            else

                F[i][j] = max(F[i - 1][j], F[i][j - 1]);

    printf("%d\n", F[m][n]);

}

Nhận xét

Code này không dùng đệ quy.

Lưu ý rằng vì F là biến toàn cục, vậy nên không cần phải gán F[i][j]=0 với i hoặc j bằng 0.

Mô tả

int F[i][j]

độ dài dãy con chung dài nhất của xâu a[1..i], b[1..j].