Đếm Xâu Chứa Mẫu (KMP Automaton)

Buổi 54 — KMP & Z-function Dynamic Programming
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề 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$.
Draft saved