Số Cách Tách Xâu Theo Từ Điển

Buổi 73-74 — Virtual CF Dynamic Programming Strings
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một xâu $S$ có độ dài $N$ và một từ điển gồm $M$ từ phân biệt (tất cả đều gồm các chữ cái Latin in thường). Hãy đếm số cách tách xâu $S$ thành một dãy liên tiếp các từ đều có mặt trong từ điể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 đầu tiên chứa xâu $S$ ($1 \le |S| \le 5000$).
  • Dòng thứ hai chứa số nguyên dương $M$ ($1 \le M \le 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa một từ trong từ điển (tổng độ dài các từ trong từ điển không quá $2 \cdot 10^5$).
Dữ liệu ra
  • Một số nguyên duy nhất là số cách tách xâu chia dư cho $10^9 + 7$.
Ví dụ
Input Output
ababc
4
ab
abab
c
abc
3
Giới hạn
  • $1 \le |S| \le 5000$
  • $1 \le M \le 10^5$, tổng độ dài từ điển $\le 2 \cdot 10^5$
Draft saved