Đây là bài toán dãy con chung dài nhất, sử dụng quy hoạch động đơn giản:
Gọi F[i][j] là chiều dài dãy con chung dài nhất của xâu a[1-i] với xâu b[1-j]. Nếu a[i] = b[j] thì F[i][j] = F[i-1][j-1]+1, else F[i][j] = max(F[i-1][j], F[i][j-1]).
Problem
https://vn.spoj.com/problems/QBSTR
https://oj.vnoi.info/problem/QBSTR
Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.
Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.
Input
Dòng 1: chứa xâu A
Dòng 2: chứa xâu B
Output
Chỉ gồm một dòng ghi độ dài xâu C tìm được
Example
Input
abc1def2ghi3
abcdefghi123
Output
10
Tutorial
Submission
QBSTR.cpp