Nén và giải nén xâu

Nguồn: CLUE OJ Độ khó: Trung bình Duyệt xâu Nén xâu (RLE)

Đề bài

Để tiết kiệm bộ nhớ, ta có thể nén xâu bằng cách thay mỗi đoạn gồm các kí tự giống nhau liên tiếp bằng số lượng kí tự của đoạn, viết liền với kí tự đó. Ví dụ xâu aaabbbbcccccc được nén thành 3a4b6c. Khi cần dùng, ta giải nén để lấy lại xâu ban đầu: 3a5C được giải nén thành aaaCCCCC.

Quy ước: khi nén, luôn ghi số lượng kể cả khi bằng 1 (ví dụ abc nén thành 1a1b1c). Chữ hoa và chữ thường là khác nhau. Số lượng có thể gồm nhiều chữ số (ví dụ 12x là $12$ chữ x).

Em hãy lập trình:

• Nén xâu ở dòng thứ nhất.
• Giải nén xâu (đã nén) ở dòng thứ hai.

Dữ liệu vào:

• Dòng thứ nhất là xâu cần nén, chỉ gồm các chữ cái tiếng Anh (hoa hoặc thường).
• Dòng thứ hai là xâu cần giải nén, gồm các cặp "số lượng + chữ cái" viết liền nhau; mỗi số lượng là số nguyên dương không có chữ số $0$ ở đầu.

Kết quả:

• Dòng thứ nhất in ra xâu đã nén.
• Dòng thứ hai in ra xâu đã giải nén.

Giới hạn:

• Độ dài mỗi xâu ở dữ liệu vào không quá $10^6$.
• Xâu sau khi giải nén có độ dài không quá $10^6$.

Subtask:

• Subtask 1 (50% số điểm): các xâu có độ dài không quá $1000$.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

aaaaabbEEE
3a5C

Ví dụ 1 – output

5a2b3E
aaaCCCCC

Ví dụ 2 – input

abc
1a1b1c

Ví dụ 2 – output

1a1b1c
abc

• Ví dụ 1: aaaaabbEEE có 5 chữ a, 2 chữ b, 3 chữ E nên nén thành 5a2b3E; 3a5C giải nén thành 3 chữ a và 5 chữ C.
• Ví dụ 2: mỗi chữ chỉ xuất hiện 1 lần liên tiếp nên vẫn ghi số 1.

Nguồn: phỏng theo bài "NÉN VÀ GIẢI NÉN" – vinhdinhcoder.net (chủ đề Xâu kí tự).

Lời mở đầu

Bài gồm hai việc ngược nhau: nén – gom mỗi đoạn kí tự giống nhau thành "số lượng + kí tự", và giải nén – làm ngược lại. Cả hai đều chỉ cần một lần duyệt xâu, nhưng có vài chỗ rất dễ sai: đoạn cuối cùng, số lượng có nhiều chữ số, và cách nối xâu khi kết quả dài tới $10^6$. Ghi chú: đề gốc không nói đoạn chỉ có 1 kí tự thì có ghi số 1 hay không; vì dòng giải nén luôn có dạng "số + chữ" nên mình chốt luôn ghi số lượng, kể cả số 1, và ghi rõ trong đề. Chữ hoa, chữ thường là khác nhau.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngđoạn liên tiếpLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–8 là xâu ngắn, test 9–20 là xâu dài tới $10^6$ kí tự.

Test	Nội dung kiểm tra
1–2	Ví dụ của đề
3–4, 7	Đoạn chỉ có 1 kí tự (phải ghi số 1), chữ hoa – thường xen kẽ aAaA
5–6, 8, 12, 18	Số lượng có nhiều chữ số (12x, 100c, 1000000a) – đọc 1 chữ số là sai
9–10, 16	Xâu $10^6$ kí tự với hàng trăm nghìn đoạn – nối xâu kiểu kq = kq + ... bị quá thời gian
11, 13–15, 17–20	Đoạn dài, xâu ngẫu nhiên đủ cỡ

Ý tưởngNén: tìm từng đoạn liên tiếp. Giải nén: ghép số rồi lặp kí tự

Nén. Đứng ở vị trí $i$, cho $j$ chạy tiếp tới khi gặp kí tự khác $s[i]$. Đoạn $s[i..j-1]$ gồm $j - i$ kí tự giống nhau, ta ghi j - i rồi ghi s[i], sau đó nhảy luôn tới $i = j$. Mỗi kí tự chỉ được $j$ đi qua một lần nên tổng cộng chỉ $O(|s|)$ bước – và đoạn cuối cùng cũng tự được xử lý, không cần "chốt" riêng.

Giải nén. Duyệt xâu nén: gặp chữ số thì ghép vào số lượng k = k * 10 + chữ_số (vì số lượng có thể gồm nhiều chữ số), gặp chữ cái thì thêm k lần chữ đó vào kết quả và đặt lại k = 0.

Nối xâu cho đúng cách

Kết quả dài tới $10^6$ kí tự. Viết kq += x hoặc kq.append(k, c) chỉ thêm vào cuối (nhanh); còn kq = kq + x tạo một xâu mới và chép lại toàn bộ kq mỗi lần – với hàng trăm nghìn đoạn sẽ chạy mất hàng chục giây.

Em nhập hai xâu rồi bấm Tiếp để xem từng đoạn được nén và từng cặp được giải nén:

s = t =

Ví dụ nhanh:

Lời giảiHai vòng lặp, mỗi vòng một lần duyệt

Hai dòng không có dấu cách nhưng mình vẫn đọc bằng getline cho chắc. Kết quả được thêm vào cuối xâu bằng += và append.

C++▶ Chạy tay từng dòng codeNén bằng hai con trỏ i, j; giải nén bằng cách ghép số lượng k.

Dữ liệu vào (stdin) – sửa thoải máiaaaaabbEEE 3a5C

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Vòng while(j < n && s[j] == s[i]) phải kiểm tra j < n trước để không đọc ra ngoài xâu.
2. to_string(x) đổi số thành xâu; giai.append(k, c) thêm k lần kí tự c vào cuối xâu.
3. Bản Python gom các mảnh vào danh sách rồi ''.join(...) một lần; c * k là xâu gồm k lần kí tự c.

Không gian$O(10^6)$

Thời gian$O(|s| + |t| + |\text{kết quả}|)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.059s. Bản Python đúng 20/20 test, chạy lâu nhất 0.575s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Không ghi số 1 khi đoạn chỉ có một kí tự	5/20	sai test 2, 3, 4, 6, 7, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20
Giải nén mà coi số lượng chỉ có 1 chữ số	10/20	sai test 5, 6, 8, 11, 12, 13, 17, 18, 19, 20
Đếm bằng biến d, gặp kí tự khác mới ghi – quên ghi đoạn cuối cùng	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Nối kết quả bằng kq = kq + ...	16/20	sai test 9, 10, 16, 19
Coi chữ hoa và chữ thường là giống nhau	11/20	sai test 4, 9, 10, 11, 13, 14, 17, 19, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.059s	Full điểm
	Python	20/20	0.575s	Full điểm
Bỏ số 1	C++	5/20	–	Mất 15 test
Số lượng 1 chữ số	C++	10/20	–	Mất 10 test
Quên đoạn cuối	C++	0/20	–	Mất 20 test
kq = kq + ...	C++	16/20	–	Mất 4 test
Không phân biệt hoa thường	C++	11/20	–	Mất 9 test

Ghi chú của mình: kỹ thuật "đứng ở $i$, cho $j$ chạy tới hết đoạn rồi nhảy $i = j$" dùng được cho mọi bài về đoạn liên tiếp giống nhau trong xâu hay mảng. Cách nén này có tên là RLE (Run-Length Encoding).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇