[Đại học Vinh - TS10 - 2025] Bài 2: Xâu tương tự
Xem dạng PDF
Gửi bài giải
Điểm:
9,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Để phát hiện mức độ trùng lặp giữa các văn bản, người ta thường kiểm tra mức độ tương tự của các đoạn văn bản được biểu diễn theo dạng các xâu ký tự. Cho hai xâu ký tự st1 và st2 có thể chứa các chữ cái thường (~a, b, ..., z~), các chữ cái hoa (~A, B, ..., Z~) và dấu cách trắng. Để tính mức độ tương tự của hai xâu st1 và st2, ta chuyển các xâu về dạng chữ cái thường hoặc chữ cái hoa sau đó tính độ tương tự theo công thức ~k = \frac{x}{y}~, trong đó:
- ~x~: số lượng chữ cái khác nhau có xuất hiện đồng thời trong cả 2 xâu
st1vàst2nhưng không tính dấu cách.
- ~y~: số lượng chữ cái khác nhau có xuất hiện ở một trong hai xâu
st1vàst2nhưng không tính dấu cách.
Yêu cầu: Viết chương trình tính độ tương tự ~k~ của hai xâu st1 và st2.
INPUT
Gồm hai dòng, mỗi dòng chứa một xâu không quá ~20000~ ký tự.
OUTPUT
In ra một dòng chứa phần nguyên của giá trị ~100 \times k~.
SAMPLE INPUT 1
The eyes
They see
SAMPLE OUTPUT 1
100
Giải thích:
- Chữ cái khác nhau có xuất hiện đồng thời cả hai xâu
st1vàst2làt,h,e,y,s, vì vậy ~x = 5~. - Chữ cái khác nhau có xuất hiện ở một trong hai xâu
st1vàst2làt,h,e,y,s, vì vậy ~y = 5~. - Độ tương tự của 2 xâu là ~k = \frac{x}{y} = \frac{5}{5} = 1~, vì vậy phần nguyên của giá trị ~100 \times k = 100~.
SAMPLE INPUT 2
Form
Formal
SAMPLE OUTPUT 2
66
Giải thích:
- Chữ cái khác nhau có xuất hiện đồng thời cả hai xâu
st1vàst2làf,o,r,m, vì vậy ~x = 4~. - Chữ cái khác nhau có xuất hiện ở một trong hai xâu
st1vàst2làf,o,r,m,a,l, vì vậy ~y = 6~. - Độ tương tự của 2 xâu là ~k = \frac{x}{y} = \frac{4}{6} = 0.6666~, vì vậy phần nguyên của giá trị ~100 \times k = 66~.
SUBTASKS
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~50\%~ | Chiều dài các xâu bé hơn ~1000~ ký tự |
| 2 | ~30\%~ | Chiều dài các xâu từ ~1000~ đến ~10000~ ký tự |
| 3 | ~20\%~ | Chiều dài các xâu từ ~10001~ đến ~20000~ ký tự |
Bình luận