Chuẩn hoá dấu cách trong xâu

Nguồn: CLUE OJ Độ khó: Dễ Duyệt xâu Xây dựng xâu mới

Đề bài

Một xâu được gọi là xâu chuẩn nếu:

• không có dấu cách thừa ở đầu và cuối xâu;
• không có hai dấu cách liền nhau.

Cho một xâu $S$, hãy in ra xâu sau khi đã chuẩn hoá (xoá các dấu cách thừa, giữ nguyên mọi kí tự khác và thứ tự của chúng).

Dữ liệu vào:

Một dòng duy nhất là xâu $S$ gồm các kí tự in được (chữ, số, dấu câu, dấu cách). Xâu có ít nhất một kí tự khác dấu cách.

Kết quả:

In ra xâu đã chuẩn hoá. Bài này chấm so khớp chính xác từng kí tự, nên dấu cách thừa (kể cả ở cuối dòng) cũng bị tính là sai.

Giới hạn:

• $1 \le |S| \le 10^6$

Subtask:

• Subtask 1 (40% số điểm): $|S| \le 1000$.
• Subtask 2 (60% 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

chao            ban

Ví dụ 1 – output

chao ban

Ví dụ 2 – input

Tin   hoc   tre

Ví dụ 2 – output

Tin hoc tre

Ví dụ trong đề gốc: xâu    Truong   THPT   Vinh   Dinh (có 3 dấu cách ở đầu và 3 dấu cách giữa hai từ) → Truong THPT Vinh Dinh.

Nguồn: phỏng theo bài "CHUẨN HOÁ XÂU" – vinhdinhcoder.net (chủ đề Xâu kí tự).

Lời mở đầu

Chuẩn hoá xâu là thao tác xuất hiện trong rất nhiều bài thi: bỏ dấu cách ở đầu, ở cuối và gộp nhiều dấu cách liền nhau thành một. Mình sẽ xây dựng xâu kết quả từng kí tự, chỉ cần duyệt một lần. Ghi chú: vì bài này kiểm tra chính các dấu cách, mình cho chấm so khớp chính xác (chấm thông thường bỏ qua dấu cách nên in nguyên xâu cũng được điểm). Đề gốc ghi độ dài không quá 1 triệu, mình giữ $|S| \le 10^6$ và đảm bảo xâu có ít nhất một kí tự khác dấu cách.

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ưởngchép kí tự, giữ 1 dấu cáchLờ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. Bài chấm so khớp chính xác từng kí tự. Test 1–10 ngắn, test 11–20 dài tới $10^6$.

Test	Nội dung kiểm tra
1–2	Ví dụ của đề
3–4, 6	Xâu đã chuẩn, một kí tự, hai từ – in nguyên xâu vẫn đúng
5, 7, 9	Dấu cách ở cả đầu và cuối – chỉ gộp dấu cách giữa thì sai
8, 10	Nhiều dấu cách giữa các từ, có dấu câu – chỉ bỏ đầu/cuối thì sai
11–16	Xâu ngẫu nhiên tới $10^6$ kí tự, số dấu cách liên tiếp khác nhau
17–20	Rất nhiều cụm 2–4 dấu cách, hoặc hàng trăm nghìn dấu cách ở đầu – xoá từng dấu cách bằng find + erase bị quá thời gian

Ý tưởngChép sang xâu mới, chỉ giữ một dấu cách sau mỗi từ

Ta tạo xâu kết quả t rỗng rồi duyệt từng kí tự c của s:

• Nếu c khác dấu cách → thêm vào t.
• Nếu c là dấu cách → chỉ thêm khi t đang không rỗng (bỏ dấu cách ở đầu) và kí tự cuối của t không phải dấu cách (bỏ dấu cách liền nhau).

Cuối cùng, nếu t kết thúc bằng dấu cách thì xoá đi (dấu cách cuối xâu).

Vì sao không xoá dần trên s?

Cách "tìm hai dấu cách liền nhau rồi erase" đúng nhưng mỗi lần erase phải dời cả phần sau của xâu, lại tìm lại từ đầu – với xâu $10^6$ kí tự có hàng trăm nghìn chỗ cần xoá thì mất hàng giờ. Chép sang xâu mới chỉ duyệt đúng một lần.

Em nhập xâu (thử gõ nhiều dấu cách) rồi bấm Tiếp:

Xâu =

Ví dụ nhanh:

Lời giảiXây dựng xâu t trong một lần duyệt

t.back() là kí tự cuối của t, t.pop_back() xoá kí tự cuối. Cả hai chỉ được gọi khi t không rỗng.

C++▶ Chạy tay từng dòng codeChép các kí tự khác dấu cách, giữ đúng 1 dấu cách sau mỗi từ, bỏ dấu cách cuối.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Python còn một cách rất gọn: print(' '.join(s.split())) – split() không tham số tự bỏ mọi dấu cách thừa. Nhưng bản vòng lặp ở trên giúp em hiểu chính xác điều gì đang xảy ra.
2. Một cách đúng khác trong C++: đọc từng từ bằng while (cin >> w) rồi in các từ cách nhau một dấu cách.
3. t += c (thêm vào cuối) rất nhanh; còn t = t + c tạo xâu mới mỗi lần nên chậm.

Không gian$O(|S|)$

Thời gian$O(|S|)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.032s. Bản Python đúng 20/20 test, chạy lâu nhất 0.185s. 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ử (bài chấm so khớp chính xác):

Cách làm sai	Đúng	Ghi chú
In nguyên xâu ban đầu	3/20	sai test 1, 2, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Chỉ gộp dấu cách liền nhau, không bỏ ở đầu/cuối	8/20	sai test 1, 5, 7, 9, 11, 12, 13, 14, 15, 16, 18, 20
Chỉ bỏ dấu cách ở đầu và cuối	6/20	sai test 1, 2, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20
Lặp find(" ") + erase	13/20	sai test 13, 14, 15, 17, 18, 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.032s	Full điểm
	Python	20/20	0.185s	Full điểm
In nguyên xâu	C++	3/20	–	Mất 17 test
Không bỏ đầu/cuối	C++	8/20	–	Mất 12 test
Không gộp giữa	C++	6/20	–	Mất 14 test
find + erase	C++	13/20	–	Mất 7 test

Ghi chú của mình: "xây xâu mới" thường đơn giản và nhanh hơn "sửa dần xâu cũ". Ghi nhớ mẫu: thêm dấu cách chỉ khi xâu kết quả không rỗng và chưa kết thúc bằng dấu cách.

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 😇