Xâu con chung dài nhất

View as PDF
Submit solution
Points: 0.06 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Xâu ký tự ~X~ được gọi là xâu con của xâu ký tự ~Y~ nếu ta có thể xoá đi một số ký tự trong xâu ~Y~ để được xâu ~X~.

Cho biết hai xâu ký tự ~A~ và ~B~ độ dài không quá ~2000~ ký tự, hãy tìm xâu ký tự ~C~ có độ dài lớn nhất và là con của cả ~A~ và ~B~.

Input

Dòng ~1~: chứa xâu ~A~

Dòng ~2~: chứa xâu ~B~

Output

Chỉ gồm một dòng ghi độ dài xâu ~C~ tìm được

Sample Input

abc1def2ghi3
abcdefghi123

Sample Output

10

Comments

Please read the guidelines before commenting.


  • -1
    zatarainbow  commented on Nov. 25, 2024, 1:17 a.m.

    include<bits/stdc++.h>

    using namespace std; string s1,s2,rt=""; long n,m,f[3009][3009],i,j,ma; int main() { iosbase::syncwith_stdio(false); cin.tie(nullptr);cout.tie(nullptr); cin>>s1>>s2; n=s1.size();m=s2.size(); s1=" "+s1; s2=" "+s2; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } cout<<f[n][m]; return 0; }


  • -7
    vdtue  commented on Aug. 20, 2024, 2:29 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -7
    frekraiko  commented on Aug. 17, 2024, 2:09 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 17
    CBNK30_dinhson  commented on July 31, 2023, 3:36 a.m.

    ảo thật đấy, từ bé đến giờ


    • 9
      CBNK30_hoangphu  commented on July 31, 2023, 3:46 a.m.

      các bạn chú ý ngôn từ của bản thân đi


      • -67
        htmanh  commented on July 31, 2023, 3:47 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


      • -33
        10tin_hangan  commented on July 31, 2023, 3:47 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


    • -51
      htmanh  commented on July 31, 2023, 3:46 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -34
      10tin_hangan  commented on July 31, 2023, 3:42 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.