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].