SỐ LỚN NHẤT

Points: 1600 (partial)

Time limit: 1.0s

Memory limit: 64M

Input: stdin

Output: stdout

Author:

TCA_Khoa

Problem type

Khi được học về LCS Tèo rất hứng thú vì học được phương pháp hay, học được cách vận dụng biến đổi các bài toán liên quan về dạng quen thuộc để ứng dụng được LCS vào để giải. Biết Tèo đang hứng thú, Tí đố Tèo một bài toán như sau:

Cho hai xâu kí tự số $X$ và $Y$ , tìm một xâu con chung có giá trị lớn nhất của hai xâu đã cho. Ví dụ $X$ = $'1003456'$ và $Y$ = $'001435'$ : Một số xâu con chung như $'00'$ , $'0035'$ , $'135'$ , $'145'$ , $\cdots$ Xâu con chung có giá trị lớn nhất là $'145'$ . Xâu con chung phải lớn nhất phải là một số không chứa số $0$ vô nghĩa.

Bạn hãy giúp Tèo viết chương trình tìm xâu con chung có giá trị lớn nhất đó để Tèo có thể kiểm tra đáp án của mình.

Input

Dòng 1 là xâu kí tự $X$
Dòng 2 là xâu kí tự $Y$

Hai xâu chỉ chứa kí tự số. Độ dài mỗi xâu số không quá $1000$ .

Output

in ra dòng 1 là độ dài của xâu con chung lớn nhất cần tìm.
Dòng thứ hai in ra xâu con chung lớn nhất theo đúng định dạng đã cho ở ví dụ bên dưới.

Example

Test 1

Input

1003456
001435

Output

3
LCS MAX NUMBER is 145

Test 2

Input

10103456
0101435

Output

5
LCS MAX NUMBER is 10145

Test 3

Input

000314
3000410

Output

2
LCS MAX NUMBER is 34

Test 4

Input

12345
6789

Output

0
LCS MAX NUMBER is NULL

Test 5

Input

60005
90204

Output

1
LCS MAX NUMBER is 0

Comments

0

itachicbh commented on 9:41 p.m. 7 jan, 2023

bài này làm lcs đc k ạ ?
đc thì ntn, tks ạ

1

vô_nhiễm commented on 11:18 a.m. 12 mar, 2022

có thể nào cho bộ nhớ lên xí xí được không ạ :) chứ bộ nhớ vậy thấy hơi căng ạ

1

NguyenfromVN commented on 3:47 a.m. 6 sep, 2021

góp ý thêm bộ test sau: 2 chuỗi, mỗi chuỗi 1000 số 1, code mình sẽ bị MLE nhưng hiện tại thì nó vẫn AC ngon lành .( $_$ ).

1

arena89 commented on 10:55 a.m. 27 jun, 2021

ai giúp mình không bị TLE test 16 với ạ. Mình cảm ơn ! arena89

1

A518Backtrack commented on 11:38 a.m. 4 aug, 2020

sao contest ni cứ chặt giới hạn bộ nhớ zậy :(((

0

TCA_Khoa commented on 12:11 p.m. 4 aug, 2020

cái này là của hhoangcpascal đổi nha =)) chơi ác

1

algorit commented on 11:21 a.m. 4 aug, 2020

Test thiếu trường hợp nha :V

2

Maowonh commented on 5:01 p.m. 3 aug, 2020

cuối cùng :(, mãi mới AC

0

lengocnga commented on 9:22 a.m. 4 aug, 2020

ai vậy

0

Maowonh commented on 9:36 a.m. 4 aug, 2020

=)) Manh11IT

0

lengocnga commented on 10:06 a.m. 4 aug, 2020

chẳng quen

0

Maowonh commented on 10:10 a.m. 4 aug, 2020

:D ??? tất nhiên là ko quen rồi, người lạ cả mà

0

tuanlinh commented on 3:53 p.m. 3 aug, 2020

sao mình làm giống TCA_Khoa nhưng dùng c++ thì bị tràn bộ nhớ ?

(đã đọc code TCA_Khoa :v)

0

hhoangcpascal commented on 3:54 p.m. 3 aug, 2020 ← edited →

Mình giảm memory limit lại đấy không phải Khoa đâu :V Tăng độ khó của game

0

tuanlinh commented on 3:56 p.m. 3 aug, 2020

mình thử nộp lại = code Khoa nhưng vẫn AC :v

0

hhoangcpascal commented on 3:57 p.m. 3 aug, 2020

Giờ nộp lại thử xem

0

tuanlinh commented on 3:58 p.m. 3 aug, 2020

vẫn AC :v

0

TCA_Khoa commented on 4:00 p.m. 3 aug, 2020

nhân phẩm

0

hhoangcpascal commented on 4:00 p.m. 3 aug, 2020

Nộp ở đâu vậy :V

0

tuanlinh commented on 4:01 p.m. 3 aug, 2020

ngoài contest

-1

hhoangcpascal commented on 4:02 p.m. 3 aug, 2020 ← edit 3 →

À há =)) thấy rồi. Tối ưu hoá mảng. Vậy thì... giảm time :3 mà thôi vậy chs khó mọi người quá :V

0

Maowonh commented on 4:49 p.m. 3 aug, 2020

:( làm vậy ai chơi

0

hhoangcpascal commented on 4:50 p.m. 3 aug, 2020

:V

0

TCA_Khoa commented on 5:17 p.m. 3 aug, 2020

a Hoàng chơi ác quá =))

0

hhoangcpascal commented on 5:19 p.m. 3 aug, 2020

:V

0

Maowonh commented on 12:50 p.m. 3 aug, 2020

sao limit bộ nhớ lại nhỏ hơn rồi :(

0

hhoangcpascal commented on 2:20 p.m. 3 aug, 2020

tránh việc duyệt trâu full test =))

0

TCA_Khoa commented on 10:28 p.m. 2 aug, 2020

ai có test LCS MAX NUMBER is NULL thì ấn nút báo cáo vấn đề giúp mình nhé :(