LCS - 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: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Cho hai xâu ký tự, tìm chiều dài của xâu con chung dài nhất của hai xâu. Xâu con của một xâu là xâu gồm các ký tự xuất hiện theo thứ tự của xâu ban đầu, nhưng không nhất thiết phải liền kề nhau. Ví dụ, 'abc', 'abg', 'bdf', 'aeg', 'acefg', v.v... là xâu con của 'abcdefg'. Vì vậy, một xâu độ dài n có thể có tới 2n xâu con khác nhau.

Dữ liệu vào:

- Dòng đầu chứa chuỗi ký tự s1 chỉ gồm các chữ cái tiếng Anh in hoa

- Dòng sau chứa chuỗi ký tự s2 chỉ gồm các chữ cái tiếng Anh in hoa

Kết quả ra: In ra độ dài xâu con chung dài nhất của s1s2.

Ví dụ

  • input
    AGGTAB
    GXTXAYB
    output
    4
Back to Top