Đếm Xâu Con Phân Biệt

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
42
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved