Đếm số cách tách từ bằng Trie
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho từ điển gồm $n$ từ phân biệt và một xâu $S$. Hãy đếm số cách tách xâu $S$ thành một dãy các từ liên tiếp đều nằm trong từ điển (một từ có thể được dùng nhiều 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 đầu chứa số nguyên $n$. $n$ dòng tiếp theo chứa các từ trong từ điển. Dòng cuối cùng chứa xâu $S$.
Dữ liệu ra
In ra số cách tách từ modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 4 a b ab ba aba |
3 |
Giới hạn
- $1 \le n \le 5000$
- $1 \le |S| \le 5000$
- Tổng độ dài các từ trong từ điển $\le 10^5$
Community Discussion