Distinct LCS

View as PDF

Submit solution

Points: 1.57 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Mew là một người thích chó, và đó là lí do vì sao Mew nuôi ~2~ còn mèo, một con đực và một con cái.

Vào một ngày đẹp trời, bỗng nhiên có một con mèo sơ sinh xuất hiện, không rõ nguồn gốc. Mew quyết định tìm hiểu xem nó có phải con của ~2~ con mèo kia không bằng cách xét nghiệm DNA của chúng.

Trong lúc xét nghiệm, Mew đã phát hiện ra một điều thú vị: ~2~ còn mèo của Mew là mèo ngoài hành tinh! Chuỗi DNA của chúng không chỉ gồm ~4~ nucleotit ~A~ ~T~ ~G~ ~X~ mà gồm ~26~ loại, được mã hóa bằng các kí tự từ ~a~ đến ~z~.

Và một điều đáng ngạc nhiên hơn nữa, chuỗi DNA của ~2~ con mèo có ~1~ số đoạn con giống ~y~ hệt nhau, trong đó đoạn con là ~1~ chuỗi các nucleotit thu được bằng cách loại bỏ đi một số nucleotit của chuỗi gen và giữ nguyên thứ tự các nucleotit còn lại. Nhưng Mew chỉ quan tâm đến đoạn con dài nhất, vì càng dài càng tiện cho việc nghiên cứu. Đồng thời Mew cũng muốn biết có bao nhiêu đoạn con chung phân biệt có độ dài đó, và muốn in ra theo thứ tự từ điển để giữ bản quyền.

Tuy nhiên do cấu hình máy tính quá cùi (Intel Core i0) nên Mew không thể thực hiện được, bạn hãy giúp Mew nhé!

Input

  • Gồm ~2~ dòng, mỗi dòng chứa ~1~ xâu là dãy nucleotit của ~2~ con mèo (độ dài xâu không quá ~100)~

Output

  • Dòng đầu tiên in ra ~N~ là số đoạn con phân biệt có độ dài lớn nhất.
  • ~N~ dòng tiếp theo, mỗi dòng in ra ~1~ xâu kết quả theo thứ tự từ điển.

Sample Input

programming
entertainment

Sample Output

2
rain
ramn

Comments

Please read the guidelines before commenting.


There are no comments at the moment.