Tìm tất cả những xâu con chung dài nhất

Submit solution
Points: 3 (partial)
Time limit: 2.0s
Memory limit: 98M
Author:
TICHPX
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Bài toán: Cho xâu x và xâu y một xâu con chung của x và y thu được bằng cách xóa đi 1 số ký tự nào đó trong x và trong y phần còn lại giữ nguyên thứ tự. Cần tìm tất cả các xâu con chung dài nhất của x và y.

Input

Nhập vào hai xâu kí tự trên hai dòng mỗi xâu không có độ dài từ 1 đến 100

Output

Tất cả các xâu con chung dài nhất của hai xâu trên được viết trên từng dòng theo thứ tự từ điển

Trong trường hợp không có xâu con chung xuất ra "khong co xau con chung"

Ví dụ 1

Input

abacab
cavadbdasf

Output

aaa
aab
aba
cab

Ví dụ 2

Input

concua
embe

Output

khong co xau con chung
tichpx

Comments


  • 0
    TICHPX  commented on Nov. 9, 2023, 12:50 p.m.

    Code tham khảo Dynamic programming

    //Tichpx- tim tat ca cac xccdn
#include<bits/stdc++.h>
using namespace std;
string x,y;
int C[105][105]={},n,m;
set<string> P[105][105];
int main()
{
    cin>>x; n=x.size(); x="$"+x;
    cin>>y; m=y.size(); y="$"+y;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) 
        if(x[i]==y[j]) 
        {
            C[i][j]=C[i-1][j-1]+1;
            if(C[i][j]==1) P[i][j].insert(string(1,x[i]));
            else for(auto s:P[i-1][j-1]) P[i][j].insert(s+x[i]);
        }
        else 
        {
            C[i][j]=max(C[i-1][j],C[i][j-1]);
            if(C[i-1][j]==C[i][j]) for(auto s:P[i-1][j]) P[i][j].insert(s);
            if(C[i][j-1]==C[i][j]) for(auto s:P[i][j-1]) P[i][j].insert(s);
        }

    for(auto s:P[n][m]) cout<<s<<"\n";
}

  • 1
    TICHPX  commented on July 17, 2021, 9:39 a.m.

    Đúng là có cả aaa


  • 1
    quang_CNTT3_K60  commented on June 19, 2021, 5:06 a.m.

    Ở ví dụ 1 xâu con aaa có được tính không thầy


    • 1
      TICHPX  commented on June 19, 2021, 1:59 p.m.

      Nếu nó xuất hiện đủ 3 ký tự a trong x và trong y


      • 2
        quang_CNTT3_K60  commented on July 16, 2021, 3:29 p.m.

        Em nghĩ là ở ví dụ 1 thiếu trường hợp "aaa" nữa thầy ạ