| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P162SUMB - Round 2B - Cắt xâu |
Cho một xâu s và một xâu t. Bạn được phép cắt xâu s thành k xâu con riêng biệt (các xâu con không cần liên tiếp nhau, nghĩa là có những phần sẽ bị bỏ đi). Hỏi xem có bao nhiêu cách cắt và trong mỗi cách cắt, cả k xâu con đều nhận xâu t làm xâu con.
Để rành mạch hơn, yêu cầu sẽ được biểu đạt bằng cách sau: Bạn cần tính có bao nhiêu cách chọn 2 mảng a1, a2, …, ak và b1, b2, … bk thỏa mãn:
- k >= 1
- 1 <= ai, bi <= |s| với mọi i từ 1 đến k
- ai <= bi với mọi i từ 1 đến k
- bi-1 < ai <= với mọi i từ 2 đến k
t là xâu con của xâu s[ai] s[ai+1]… s[bi] với mọi i từ 1 đến k.
Input
Gòm 2 dòng, lần lượt bao gồm xâu s và xâu t (1 <= |s|, |t| <= 105). Mỗi xâu chỉ bao gồm chữ cái latin viết thường
Output
In ra kết quả bài toán – là số cách thỏa mãn sau khi lấy mod cho 10^9 + 7
Example
Input: ddd
d Output: 12
Input: ababa
aba Output: 5
| Được gửi lên bởi: | adm |
| Ngày: | 2016-07-14 |
| Thời gian chạy: | 1s-2s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
