LCS - Tìm xâu con chung dài nhất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 5.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Cho hai xâu, hãy tìm xâu con chung dài nhất của hai xâu đó.

Dữ liệu vào

Dòng đầu tiên chứa duy nhất một số T ≤ 30 là số lượng bộ test.
Mỗi test gồm 2 dòng, mỗi dòng chứa một xâu gồm các kí tự trong ‘a’ đến ‘z’ viết liền nhau, giới hạn độ dài không quá 5000.

Kết quả

Ghi ra T dòng, mỗi dòng là kết quả tương ứng cho một test là độ dài xâu con chung dài nhất tìm được

Ví dụ

Input

1
wigwwnydtyo
kwmmka

Output

1


Nguồn: ĐPT '1819

Back to Top