Tách xâu theo từ điển
Points
95
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một xâu $S$ độ dài $N$ và một từ điển gồm $K$ từ phân biệt $w_1, w_2, \dots, w_K$ (chỉ gồm các chữ cái tiếng Anh viết 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ừ thuộc từ điển (mỗi từ có thể dùng nhiều lần). Kết quả lấy phần dư cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên là xâu $S$ ($1 \le |S| \le 5000$).
- Dòng thứ hai chứa số nguyên $K$ ($1 \le K \le 10^5$).
- $K$ dòng tiếp theo, mỗi dòng là một từ $w_i$ (tổng độ dài các từ không vượt quá $10^5$).
Dữ liệu ra
- Một số nguyên duy nhất là số cách tách xâu $S$ modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| ababc 4 ab abab c abc |
3 |
Giới hạn
- $1 \le |S| \le 5000$, tổng độ dài các từ $\le 10^5$
Community Discussion