Tách xâu theo từ điển

Buổi 77 — Tổng kết Dynamic Programming Strings
Points
95
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved