Hiệu chỉnh văn bản

Điểm: 0,20 (OI)

Giới hạn thời gian: 0.38s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

PTNK 10 Final Exam - Semester I, 2008

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho trước một số nguyên ~K~ và hai văn bản dưới dạng hai xâu ~S~ và ~P~ (có độ dài không quá ~50~ ký tự), chỉ gồm các chữ cái in thường ('a' ...'z').

Người ta hiệu chỉnh cả hai văn bản theo quy tắc sau: tìm xâu con (nghĩa là một đoạn gồm các ký tự liên tiếp) chung dài nhất của hai xâu ~S~ và ~P~. Sau đó nếu xâu con chung này có độ dài ~> = K~ thì xóa xâu con chung này khỏi ~S~ và ~P~.

Trong trường hợp có nhiều xâu con chung dài nhất, người ta chọn xâu để xóa theo quy tắc sau:

Chọn xâu con chung dài nhất có vị trí trái nhất thuộc xâu ~S~
Nếu xâu này vẫn xuất hiện nhiều lần ở xâu ~P~, chọn xâu có vị trí trái nhất thuộc xâu ~P~

Quá trình này được lặp lại cho đến khi ~S~ và ~P~ không còn xâu con chung nào có độ dài ~> = K~.

Bạn hãy lập trình thực hiện quá trình hiệu chỉnh văn bản trên và in ra số bước hiệu chỉnh, xâu ~S~ và ~P~ cuối cùng.

Input

Dòng 1: ~K~
Dòng 2: ~S~
Dòng 3: ~P~

Output

Dòng 1: số bước
Dòng 2: ~S~ sau khi hiệu chỉnh
Dòng 3: ~P~ sau khi hiệu chỉnh

Sample Input

2
aabhh
haahaa

Sample Output

2
b
aa

Note

Bước 1: ~S~ = aabhh, ~P~ = haahaa

Bước 2: ~S~ = bhh, ~P~ = hhaa

Kết thúc: ~S~ = b, ~P~ = aa

Đến đây ~S~ và ~P~ không còn xâu con chung nào có độ dài ~\leq 2~. Ta kết thúc quá trình hiệu chỉnh văn bản.

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.