Đếm Xâu Chứa Mẫu (KMP Automaton)
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Đề bài
Cho số nguyên dương $N$ và xâu mẫu $P$ chỉ gồm các chữ cái tiếng Anh viết thường ('a'–'z').
Hãy đếm số lượng xâu ký tự độ dài $N$ (chỉ gồm các chữ cái 'a'–'z') có chứa $P$ như một xâu con liên tiếp ít nhất một lần. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $10^9 + 7$.
Dữ liệu vào
- Dòng 1: số nguyên $N$ ($1 \le N \le 1000$).
- Dòng 2: xâu $P$ ($1 \le |P| \le 100$).
Dữ liệu ra
- Một số nguyên duy nhất là số lượng xâu thỏa mãn modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 2\nab | 1 |
| 3\naa | 51 |
Giới hạn
- $1 \le N \le 1000$, $1 \le |P| \le 100$.
Community Discussion