Độ phân biệt của hai xâu

View as PDF

Submit solution

Points: 5.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Hai xâu ~X~ và ~Y~ có cùng độ dài ~n~ , độ phân biệt của hai xâu là số lượng các vị trí ~i~ thỏa mãn ~X[i]~ khác ~Y[i]~ . Ví dụ hai xâu ~abxy~ và ~ayxd~ có độ phân biệt là 2 vì có ~X[2]~ ~\neq~ ~Y[2]~ và ~X[4]~ ~\neq~ ~Y[4]~.

Cho 2 xâu ~X~ và ~Y~ có cùng độ dài gồm các chữ cái in thường, trong mỗi xâu có thể có một số vị trí bị mờ được ghi bằng các kí tự '?', ở vị trí bị mờ có thể thay bằng một chữ cái bất kì.

Yêu cầu: Xác định độ phân biệt nhỏ nhất và độ phân biệt lớn nhất của hai xâu đã cho khi thay thế các vị trí bị mờ bằng các chữ cái thích hợp.

Dữ liệu vào: gồm hai dòng ghi lần lượt xâu ~X~ và xâu ~Y~ có độ dài không vượt quá 255 kí tự.

Kết quả : Ghi ra lần lượt độ phân biệt nhỏ nhất và độ phân biệt lớn nhất của hai xâu.

Ví dụ:
Input
?ab?c
aca?w
Output
3 5

Ràng buộc:

  • Có 30% test trong các xâu không có kí tự mờ tương ứng 30% số điểm;
  • Có 30% test chỉ có một xâu có kí tự mờ tương ứng số điểm;
  • Có 40% test không có ràng buộc gì thêm.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.