Xâu con chung dài nhất 2

Xem PDF



Thời gian:
Pascal 1.75s
Python 3 2.0s
Bộ nhớ:
Pascal 32M
Python 3 64M

Tác giả:
Dạng bài
Điểm: 400 (p) Thời gian: 0.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Input

  • Gồm hai dòng
  • Dòng thứ nhất chứa xâu \(S\).
  • Dòng thứ hai chứa xâu \(T\).

Output

  • In ra độ dài xâu con chung dài nhất cần tìm.
    Chú ý: Một xâu con của một xâu \(X\) bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu \(X\) và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(|S|, |T| \le 10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(|S|, |T| \le 10^4\).

Example

Test 1

Input
axyb
abyxb 
Output
3

Nguồn: Cấp độ khó hơn của bài Xâu con chung dài nhất của jumptozero


Bình luận


  • 0
    NEIK    7:06 p.m. 10 Tháng 5, 2021

    làm sao để ko tle ạ 🙂


    • 1
      SPyofgame    7:31 p.m. 10 Tháng 5, 2021

      1 trong những cách là qhđ đảo nhãn, còn không thì tối ưu không gian và thời gian tính là được bạn

      6 bình luận nữa