C11STR - String
Giới hạn- Thời gian: 0.329s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho 2 xâu ký tự S và T trong đó S chỉ bao gồm các ký tự 'a' -> 'z' còn T chỉ bao gồm các ký tự 'a' -> 'z' và 2 ký tự đặc biệt là '?' và '*'.
Một ký tự '*' trong xâu T có thể đại diện cho 1 số lượng bất kỳ (có thể bằng 0) các ký tự 'a' -> 'z'.
Một ký tự '?' trong xâu T có thể đại diện cho đúng 1 ký tự trong số các ký tự 'a' -> 'z'.
Một xâu X gọi là thỏa mãn định dạng T nếu ta có thể thay các ký tự '*' và '?' trong xâu T để thu được xâu X.
Ví dụ
T = '*bc?' sẽ có các xâu X thỏa mãn như 'abca' , 'bca', 'bcd', 'aaaaabcz', ...
Trọng số của một xâu được tính bằng tổng trọng số của các ký tự có trong đó với quy ước 'a' = 1, 'b' = 2, 'c' = 3, ... 'z' = 26.
Yêu cầu
Hãy tìm xâu X là xâu con liên tiếp của xâu S mà X thỏa mãn định dạng T và có trọng số là nhỏ nhất.
Input
Gồm 1 dòng chứa 2 xâu T và S ( 1 ≤ |S| ≤ 10000, |T| ≤ 1000 )
Output
Ghi ra trọng số của xâu X tìm được, hoặc ghi ra -1 nếu không có xâu X nào thỏa mãn.
Ví dụ
Input a?a alabala Output 4 Giải thích aba là xâu có trọng số nhỏ nhất tìm được. Input a*c?a axcbaabcbax Output 9 Giải thích abcba có trọng số nhỏ hơn axcba
- Người up: yenthanh132