Đề bài: http://vn.spoj.com/problems/VMRR/
Có một điều bí mật, mà xưa nay chỉ được lưu truyền giữa các admin VNOI, là RR có những sở thích rất khác người. Không chỉ dừng lại ở việc ngồi ngắm bảng rank của các kỳ thi trên mạng hàng tiếng đồng hồ hay ngồi học thuộc tên của các coder nổi tiếng thế giới, RR còn có sở thích tìm tên mình trong những chuỗi văn bản dài…
Nhiều khi, việc tìm tên mình mất rất nhiều thời gian, thậm chí có thể tốn nhiều ngày mà vẫn đếm nhầm. Các bạn hãy giúp RR giải quyết vấn đề này một cách tổng quát hơn nhé.
Yêu cầu
Cho một xâu S và 2 ký tự X và Y. Đếm xem chuỗi con XY xuất hiện bao nhiêu lần trong S (hai ký tự X và Y không cần liên tiếp nhưng cần xuất hiện đúng thứ tự (X trước Y)).
Input
Dòng 1: Xâu S.
Dòng 2: X và Y.
Output
Gồm 1 số nguyên duy nhất là kết quả của bài toán.
Giới hạn
Xâu S chứa không quá 10^6 ký tự.
Tất cả các ký tự trong đề bài có mã ASCII từ 32 đến 255.

————————
Bài này khá đơn giản. Chúng ta chỉ việc duyệt chuỗi và nếu gặp Y thì tăng KQ lên countX, trong đó countX là số ký tự X xuất hiện trước đó.
Lưu ý:
+ Trong bài này KQ có thể rất lớn nên chúng ta phải dùng kiểu long long (trong C/C++) cho KQ, với pascal ta nên chọn kiểu Qword.
+ Khi nhập dữ liệu chú ý xâu có thể có khoảng trắng

Advertisements