[Đạ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ự st1st2 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 st1st2, 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 st1st2 như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 st1st2 như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 st1st2.

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 st1st2t, 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 st1st2t, 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 st1st2f, 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 st1st2f, 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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.