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

View as PDF

Submit solution

Points: 400 (partial)
Time limit: 0.5s
Pascal 1.75s
Python 3 2.0s
Memory limit: 32M
Python 3 64M
Input: stdin
Output: stdout

Author:
Problem types

Cho hai xâu \(S\) và \(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\) và \(T\).

Dữ liệu vào: Gồm hai dòng

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

Kết quả: 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.

Ví dụ:

Input:

axyb
abyxb

Output:

3

Giới hạn:

  • \(50\)% số test đầu tiên tương ứng với \(50\)% số điểm có \(|S|, |T| \le 10^3\).
  • \(50\)% số test còn lại tương ứng với \(50\)% số điểm có \(|S|, |T| \le 10^4\).

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


View comments (15)

Comments


  • 0
    NEIK  commented on 7:06 p.m. 10 may, 2021

    làm sao để ko tle ạ :)


    • 1
      SPyofgame  commented on 7:31 p.m. 10 may, 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


  • 0
    LeVanThuc  commented on 12:52 p.m. 5 aug, 2020

    Cho em hỏi bị lỗi Failed initializing là bị gì thế ạ?


  • 0
    SPyofgame  commented on 7:59 a.m. 5 aug, 2020

    À rế, có cả trường hợp \(|S| = 0\) sao anh >.<


  • 0
    SPyofgame  commented on 10:49 p.m. 4 aug, 2020 edit 2

    Answer là Checking............................. là sao ạ :(


    • 1
      TCA_Khoa  commented on 7:13 a.m. 5 aug, 2020

      tránh if test :v


      • 0
        SPyofgame  commented on 7:46 a.m. 5 aug, 2020

        Em suggest sài queries đê anti-iftest thay vì cách này :( ?


        • 0
          hhoangcpascal  commented on 9:14 a.m. 5 aug, 2020

          Cái j đơn giản hơn thì làm cái đó


        • 0
          TCA_Khoa  commented on 7:50 a.m. 5 aug, 2020

          cái này là a hhoangcpascal làm chứ k phải e


  • 0
    algorit  commented on 10:33 a.m. 4 aug, 2020

    :) vl anh

    vler memory


  • 0
    TCA_Khoa  commented on 8:49 a.m. 4 aug, 2020

    a vinhntndu đọc memory :)


    • 1
      vinhntndu  commented on 8:49 a.m. 4 aug, 2020

      :) hiểu