🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Gần Tết, thầy Sơn về phụ ba mẹ làm bảng hiệu mới cho chiếc ghe bán trái cây ở chợ nổi Phong Điền. Trong thùng đồ nghề có một dải chữ cái gỗ được xếp sẵn thành một hàng, đọc từ trái sang phải là xâu ~S~ gồm ~n~ chữ cái latin thường.

Thầy Sơn sẽ chọn ra một số chữ cái (ít nhất một chữ) trong dải, giữ nguyên thứ tự trái sang phải của chúng, rồi ghép lại thành dòng chữ trên bảng hiệu. Nói cách khác, dòng chữ là một xâu con (không nhất thiết liên tiếp) của ~S~. Hai cách chọn được coi là khác nhau nếu tập vị trí các chữ được chọn khác nhau, kể cả khi dòng chữ thu được giống nhau.

Dân buôn bán trên sông rất kiêng chữ "lỗ". Má thầy Sơn dặn: dòng chữ trên bảng hiệu tuyệt đối không được chứa xâu ~P~ (gồm ~m~ chữ cái latin thường) như một đoạn liên tiếp. Ví dụ với ~P =~ lo, dòng chữ olol không được phép vì có đoạn lo ở giữa, còn dòng chữ oll thì được phép.

Hãy giúp thầy Sơn đếm số cách chọn hợp lệ. Vì kết quả có thể rất lớn, chỉ cần in ra phần dư khi chia cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu tiên chứa xâu ~S~ ~(1 \le n = |S| \le 10^5)~.
• Dòng thứ hai chứa xâu ~P~ ~(1 \le m = |P| \le 100)~.

Cả hai xâu chỉ gồm các chữ cái latin thường từ a đến z.

Kết quả

Một số nguyên duy nhất là số cách chọn hợp lệ, lấy phần dư khi chia cho ~10^9 + 7~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~n \le 20~.
• Subtask 2 (~30\%~ số điểm): các chữ cái của ~P~ đôi một khác nhau.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

lolo
lo

Sample Output 1

7

Giải thích

Có ~2^4 - 1 = 15~ cách chọn. Các cách hợp lệ là: ~4~ cách chọn một chữ; chọn vị trí ~\{1, 3\}~ được ll, ~\{2, 3\}~ được ol, ~\{2, 4\}~ được oo. Mọi cách chọn khác đều tạo ra dòng chữ chứa lo (chẳng hạn ~\{1, 2\}~ được lo, ~\{2, 3, 4\}~ được olo). Vậy có ~7~ cách.

Sample Input 2

ababa
aba

Sample Output 2

22

Giải thích

Có ~2^5 - 1 = 31~ cách chọn, trong đó có ~9~ cách cho dòng chữ chứa đoạn aba:

• ~4~ cách cho đúng aba: vị trí ~\{1,2,3\}, \{1,2,5\}, \{1,4,5\}, \{3,4,5\}~;
• ~\{1,2,3,4\}~ → abab, ~\{1,2,3,5\}~ → abaa, ~\{1,3,4,5\}~ → aaba, ~\{2,3,4,5\}~ → baba, ~\{1,2,3,4,5\}~ → ababa.

Mỗi tập vị trí chỉ được tính một lần. Đáp án là ~31 - 9 = 22~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).