Đếm Xâu Con Phân Biệt
Points
42
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một chuỗi $S$ độ dài $N$ chỉ gồm các chữ cái Latinh thường. Hãy đếm số lượng xâu con (không nhất thiết liên tiếp, khác rỗng) phân biệt của $S$. Kết quả lấy phần dư khi chia cho $10^9 + 7$.
Cấu trúc con tối ưu: gọi $dp[i]$ là số xâu con phân biệt (tính cả xâu rỗng) tạo từ $i$ ký tự đầu tiên, và $last[c]$ là vị trí xuất hiện gần nhất của ký tự $c$. Khi thêm ký tự $s_i$, ta có $dp[i] = 2 \cdot dp[i-1] - dp[last[s_i] - 1]$.
Dữ liệu vào
- Một dòng duy nhất chứa chuỗi $S$ ($1 \le |S| \le 10^5$).
Dữ liệu ra
- In ra số xâu con khác rỗng phân biệt modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| abc | 7 |
| aba | 6 |
Giới hạn
- $1 \le |S| \le 10^5$
Community Discussion