Giải mã chữ viết của người Maia
Đề bài
Công việc giải mã chữ viết của người MAIA là khó khăn hơn người ta tưởng nhiều. Trải qua hơn 200 năm mà người ta vẫn hiểu rất ít về các chữ viết này. Chỉ trong 3 thập niên gần đây do công nghệ phát triển việc giải mã này mới có nhiều tiến bộ.
Chữ viết Maia dựa trên các ký hiệu nhỏ gọi là nét vẽ, mỗi nét vẽ tương ứng với một âm giọng nói. Mỗi từ trong chữ viết Maia sẽ bao gồm một tập hợp các nét vẽ như vậy kết hợp lại với nhiều kiểu dáng khác nhau. Mỗi nét vẽ có thể hiểu là một ký tự ta hiểu ngày nay.
Một trong những vấn đề lớn khi giải mã chữ Maia là thứ tự đọc các nét vẽ. Do người Maia trình bày các nét vẽ này không theo thứ tự phát âm, mà theo cách thể hiện của chúng. Do vậy nhiều khi đã biết hết các nét vẽ của một từ rồi nhưng vẫn không thể tìm ra được chính xác cách ghi và đọc của từ này.
Các nhà khảo cổ đang đi tìm kiếm một từ đặc biệt $W$. Họ đã biết rõ tất cả các nét vẽ của từ này nhưng vẫn chưa biết các cách viết ra của từ này. Vì họ biết có các thí sinh IOI'06 sẽ đến nên muốn sự trợ giúp của các sinh viên này. Họ sẽ đưa ra toàn bộ $g$ nét vẽ của từ $W$ và dãy $S$ tất cả các nét vẽ có trong hang đá cổ. Bạn hãy giúp các nhà khảo cổ tính xem có bao nhiêu khả năng xuất hiện từ $W$ trong hang đá.
Yêu cầu: Hãy viết chương trình, cho trước các ký tự của từ $W$ và dãy $S$ các nét vẽ trong hang đá, tính tổng số khả năng xuất hiện của từ $W$ trong dãy $S$, nghĩa là số lần xuất hiện một hoán vị các ký tự của dãy $g$ ký tự trong $S$. Lưu ý: từ $W$ sẽ xuất hiện dưới dạng chuỗi con liên tiếp trong $S$.
Các ràng buộc:
- $1 \le g \le 3000$, $g$ là số nét vẽ trong $W$.
- $g \le |S| \le 3\,000\,000$, $|S|$ là số các nét vẽ của dãy $S$.
- 50% số test đầu tiên có $g \le 10$, $|S| \le 20$; 50% số test còn lại không có giới hạn gì thêm.
Input:
- Dòng 1: chứa 2 số $g$ và $|S|$ cách nhau bởi dấu cách.
- Dòng 2: chứa $g$ ký tự liền nhau là các nét vẽ của từ $W$. Các ký tự hợp lệ là
'a'–'z'và'A'–'Z'. Chữ in hoa và in thường là khác nhau. - Dòng 3: chứa $|S|$ ký tự là dãy các nét vẽ tìm thấy trong hang. Các ký tự hợp lệ là
'a'–'z'và'A'–'Z'. Chữ in hoa và in thường là khác nhau.
Output: chứa đúng 1 số là số khả năng xuất hiện của từ $W$ trong dãy $S$.
4 11
cAda
AbrAcadAbRa2Giải thích ví dụ: $W$ = cAda gồm các ký tự A, a, c, d (mỗi ký tự 1 lần). Trong $S$ = AbrAcadAbRa có đúng 2 đoạn con liên tiếp dài 4 là hoán vị của $W$: Acad (vị trí 3–6, tính từ 0) và cadA (vị trí 4–7). Chú ý đoạn adAb không được vì có b thay cho c.
Lời mở đầu
Đây là bài Writing của kỳ thi IOI 2006 – một bài "nhập môn" rất đẹp cho kỹ thuật cửa sổ trượt. Hai xâu là hoán vị của nhau khi và chỉ khi số lần xuất hiện của từng ký tự là như nhau, nên ta chỉ cần biết bảng đếm ký tự của từng đoạn con dài $g$. Mà hai đoạn con liền nhau chỉ khác nhau đúng 1 ký tự vào và 1 ký tự ra – đó chính là chỗ để cửa sổ trượt phát huy sức mạnh. Mình sẽ đi từ cách ngây thơ nhất tới cách $O(|S|)$ để các bạn thấy rõ mỗi bước tối ưu bỏ đi được phần việc thừa nào.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, đúng như đề nói: 50 test đầu nhỏ, 50 test sau lớn hết cỡ. Mình kiểm tra thì mọi test đều có độ dài $W$, $S$ đúng bằng $g$, $|S|$ ghi ở dòng đầu.
| Test | g | |S| | Số loại ký tự trong S | Đáp án |
|---|---|---|---|---|
| 1 – 50 | 2 … 10 | 7 … 20 | 2 … 12 | 0 … 17 |
| 51 – 75 | 3 000 … 3 000 | 1 000 000 … 1 000 000 | 52 … 52 | 4 … 47 |
| 76 – 100 | 3 000 … 3 000 | 3 000 000 … 3 000 000 | 1 … 52 | 5 … 2 997 001 |
- Test 1 – 50: $g \le 10$, $|S| \le 20$, xâu chỉ dùng vài chữ cái nên có khá nhiều đoạn khớp (đáp án tới 17), có cả test đáp án bằng 0.
- Test 51 – 75: $g = 3000$, $|S| = 10^6$, dùng đủ cả 52 chữ cái.
- Test 76 – 100: $g = 3000$, $|S| = 3 \cdot 10^6$ (tối đa). Riêng test 100 cả $W$ và $S$ chỉ gồm một loại ký tự, nên mọi đoạn đều khớp: đáp án $3\,000\,000 - 3000 + 1$ $= 2\,997\,001$.
Bảng subtask và cách nào ăn được (kết quả chạy thật ở từng cách bên dưới):
| Subtask | Điều kiện | Test | Cách 1 | Cách 2 | Cách 3 |
|---|---|---|---|---|---|
| 1 (50%) | $g \le 10$, $|S| \le 20$ | 1 – 50 | ✔ | ✔ | ✔ |
| 2 (50%) | không giới hạn thêm | 51 – 100 | ✘ | ✔ | ✔ |
Cách 1Sắp xếp từng đoạn con – ăn subtask 1
Hai xâu là hoán vị của nhau khi và chỉ khi sắp xếp lại thì giống hệt nhau. Vậy ta sắp xếp $W$ một lần, rồi với mỗi vị trí bắt đầu $i$ ($0 \le i \le |S| - g$) cắt đoạn con S.substr(i, g), sắp xếp nó và so sánh với $W$ đã sắp xếp.
- Vòng lặp chạy
i + g <= nđể đoạnS[i..i+g-1]không vượt quá cuối xâu. - So sánh 2
stringbằng==là so sánh từng ký tự, mất $O(g)$.
Kết quả chạy thật: bản C++ đúng 50/100 test – trọn subtask 1 (test 1 – 50, mỗi test dưới 0.01 giây). Mọi test của subtask 2 đều quá thời gian: với $|S| = 10^6$, $g = 3000$ phải sắp xếp gần $10^6$ đoạn, mỗi đoạn 3000 ký tự – cỡ $3 \cdot 10^{10}$ phép tính. Bản Python cũng đúng 50/100.
Ý tưởngBảng đếm ký tự và cửa sổ trượt
Cách 1 lãng phí ở chỗ: đoạn bắt đầu tại $i$ và đoạn bắt đầu tại $i+1$ có tới $g - 1$ ký tự chung, vậy mà ta sắp xếp lại từ đầu. Thay vì sắp xếp, ta dùng bảng đếm: cnt[c] = số lần ký tự $c$ xuất hiện. Hai xâu là hoán vị của nhau khi và chỉ khi bảng đếm của chúng bằng nhau ở mọi ký tự.
S[i] đi vào (tăng đếm), ký tự S[i - g] đi ra (giảm đếm). Mỗi bước chỉ sửa 2 ô của bảng đếm, thay vì xây lại cả bảng.Vậy còn việc so sánh 2 bảng? Có 52 ký tự nên so sánh trực tiếp mất 52 phép mỗi bước (Cách 2) – đã đủ nhanh. Nhưng ta còn làm tốt hơn: giữ biến lech = số ký tự đang có số lần khác nhau giữa cửa sổ và $W$. Mỗi lần sửa 1 ô của bảng, lech chỉ có thể thay đổi ở đúng ký tự đó, nên cập nhật được trong $O(1)$; cửa sổ là hoán vị của $W$ khi và chỉ khi lech == 0 (Cách 3).
Em nhập $W$ và $S$ rồi bấm Tiếp để xem cửa sổ trượt và bảng đếm thay đổi từng bước:
Cách 2Cửa sổ trượt + so sánh 52 ô đếm
Mình đổi ký tự thành chỉ số $0..51$ bằng hàm id (chữ thường $0..25$, chữ hoa $26..51$), đếm $W$ vào cw, còn cs là bảng đếm của cửa sổ hiện tại. Khi i >= g - 1 thì cửa sổ S[i-g+1..i] đã đủ $g$ ký tự, ta so sánh 52 ô của cs và cw.
for(c...) khung chỉ dừng ở các ký tự có mặt trong W hoặc S; các ô khác luôn là 0 = 0 nên máy chạy qua rất nhanh.cs[id(S[i])]++đặt trước rồi mới bỏS[i - g]ra: sau 2 dòng này cửa sổ đúng làS[i-g+1..i], có đúng $g$ ký tự.- Vòng
for(c...)dừng ngay (break) khi gặp ô khác nhau, nên thực tế thường chạy ít hơn 52 lần. - Python: so sánh 2 list bằng
cs == cwchạy trong C nên khá nhanh, nhưng vòng lặp chính 3 triệu lần vẫn là Python thuần.
Kết quả chạy thật: bản C++ đúng 100/100 test, test chậm nhất (test 100, $|S| = 3 \cdot 10^6$) chạy 0.09 giây. Bản Python đúng 75/100: các test $|S| = 10^6$ còn qua được, nhưng phần lớn test $|S| = 3 \cdot 10^6$ bị quá 1 giây vì vòng lặp 3 triệu lần trong Python quá chậm.
Cách 3Đếm số ký tự lệch – O(|S|)
Mình gộp 2 bảng đếm thành một mảng hiệu d[c] = (số lần $c$ trong cửa sổ) − (số lần $c$ trong $W$). Ban đầu cửa sổ rỗng nên d[c] = −(số lần c trong W). Biến lech đếm số ký tự có d[c] != 0. Hàm them(c, v) cộng v vào d[c] và sửa lech:
- Nếu trước khi cộng
d[c] == 0thì ký tự $c$ đang khớp và sắp bị lệch →lech++. - Nếu sau khi cộng
d[c] == 0thì $c$ vừa khớp trở lại →lech--.
Hai trường hợp không thể xảy ra cùng lúc vì v khác 0. Cửa sổ đủ $g$ ký tự mà lech == 0 nghĩa là mọi ký tự đều khớp → đếm 1 khả năng.
- Mảng
d[128]đánh chỉ số thẳng bằng mã ASCII của ký tự nên không cần hàmid. - Gọi
them(W[i], -1)cho mọi ký tự của $W$ để khởi tạo; lúc nàylech= số ký tự khác nhau của $W$. - Đáp án tối đa là $|S| - g + 1 \le 3 \cdot 10^6$ nên
intlà đủ (test 100 có đáp án lớn nhất $2\,997\,001$).
Kết quả chạy thật: bản C++ đúng 100/100 test, test chậm nhất chỉ 0.03 giây – nhanh hơn cả Cách 2 vì mỗi bước chỉ sửa vài biến. Bản Python đúng 73/100, cũng bị quá thời gian ở các test $|S| = 3 \cdot 10^6$ (Python thuần khó chạy kịp 3 triệu vòng lặp có rẽ nhánh trong 1 giây).
lech) để so sánh 2 bảng đếm trong $O(1)$ còn dùng lại ở rất nhiều bài tìm hoán vị / anagram khác.
Nhận xét
Đăng nhận xét