Bài tập | NEU OJ

Phân tích tần suất (frequency analysis) là kỹ thuật nền tảng để thám mã các hệ mật mã cổ điển (Caesar, Vigenère, ...): kẻ tấn công dựa vào việc chữ cái nào xuất hiện nhiều/ít trong bản mã để suy đoán chữ cái tương ứng trong bảng chữ cái tự nhiên.

Cho một đoạn văn bản (có thể gồm chữ hoa, chữ thường, chữ số, dấu câu, khoảng trắng). Bước đầu tiên của phân tích tần suất là chuẩn hóa văn bản: chỉ giữ lại các chữ cái tiếng Anh $A \ldots Z$ , coi chữ hoa và chữ thường là như nhau (đưa tất cả về chữ hoa), loại bỏ mọi ký tự khác (số, dấu câu, khoảng trắng, ký tự có dấu, ...).

Hãy đếm số lần xuất hiện của mỗi chữ cái trong văn bản đã chuẩn hóa.

Ví dụ: với văn bản Hello, World! 123, sau khi chuẩn hóa ta được chuỗi HELLOWORLD gồm 10 chữ cái. Trong đó L xuất hiện 3 lần, O xuất hiện 2 lần, còn D, E, H, R, W mỗi chữ xuất hiện 1 lần.

Định dạng đầu vào:
Một dòng duy nhất chứa văn bản cần phân tích, độ dài tối đa $10^5$ ký tự (có thể chứa khoảng trắng, có thể là chuỗi rỗng).
Định dạng đầu ra:
- Dòng đầu tiên: số nguyên $N$ — tổng số chữ cái sau khi chuẩn hóa.
- Nếu $N = 0$ : không in gì thêm.
- Nếu $N > 0$ : với mỗi chữ cái CÓ xuất hiện (số lần $> 0$ ), in một dòng theo định dạng <CHỮ> <SỐ_LẦN> <TẦN_SUẤT>% trong đó tần suất $= \text{số\_lần}/N \times 100$ , làm tròn đúng 2 chữ số thập phân. Các dòng được sắp xếp giảm dần theo số lần xuất hiện; nếu bằng nhau, sắp xếp theo thứ tự bảng chữ cái tăng dần.
Ví dụ với Hello, World! 123, output là:
```
10
L 3 30.00%
O 2 20.00%
D 1 10.00%
E 1 10.00%
H 1 10.00%
R 1 10.00%
W 1 10.00%
```

solution

Đề bài: [An toàn thông tin] Đếm và sắp xếp tần suất chữ cái