LCS Medium

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai xâu \(S\) và \(T\) chỉ gồm các chữ cái in thường. Tìm độ dài xâu con chung dài nhất (Subsequence) của hai xâu \(S\) và \(T\).

Input

Dòng đầu tiên chứa xâu \(S\).
Dòng thứ hai chứa xâu \(T\).

Output

In ra một số nguyên dương duy nhất là độ dài xâu con chung dài nhất của \(S\) và \(T\).

Example

Test 1

Input

abab
baba

Output

Note

\(|S| \geq |T|\).
\(|T| \leq 5.10^3, |S|\ \leq 10^6\).

Bình luận (2)

Tải bình luận...