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

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
PTNK 10 Final Exam - Semester I, 2008
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho trước một số nguyên ~K~ và hai văn bản dưới dạng hai xâu ~S~ và ~P~ (có độ dài không quá ~50~ ký tự), chỉ gồm các chữ cái in thường ('a' ...'z').

Người ta hiệu chỉnh cả hai văn bản theo quy tắc sau: tìm xâu con (nghĩa là một đoạn gồm các ký tự liên tiếp) chung dài nhất của hai xâu ~S~ và ~P~. Sau đó nếu xâu con chung này có độ dài ~> = K~ thì xóa xâu con chung này khỏi ~S~ và ~P~.

Trong trường hợp có nhiều xâu con chung dài nhất, người ta chọn xâu để xóa theo quy tắc sau:

  • Chọn xâu con chung dài nhất có vị trí trái nhất thuộc xâu ~S~
  • Nếu xâu này vẫn xuất hiện nhiều lần ở xâu ~P~, chọn xâu có vị trí trái nhất thuộc xâu ~P~

Quá trình này được lặp lại cho đến khi ~S~ và ~P~ không còn xâu con chung nào có độ dài ~> = K~.

Bạn hãy lập trình thực hiện quá trình hiệu chỉnh văn bản trên và in ra số bước hiệu chỉnh, xâu ~S~ và ~P~ cuối cù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

Bước 1: ~S~ = aabhh, ~P~ = haahaa

Bước 2: ~S~ = bhh, ~P~ = hhaa

Kết thúc: ~S~ = b, ~P~ = aa

Đến đây ~S~ và ~P~ không còn xâu con chung nào có độ dài ~\leq 2~. Ta kết thúc quá trình hiệu chỉnh văn bản.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.