Cho bảng chữ Σ và biểu thức chính quy R. Với mỗi truy vấn n, đếm số chuỗi độ dài đúng n thuộc L(R). Xây DFA một lần rồi trả lời từng truy vấn bằng quy hoạch động.
Ví dụ với R=(a|b)*abb: n=3 → 1; n=4 → 3.
Dòng 1: Σ. Dòng 2: R. Dòng 3: số truy vấn q. q dòng, mỗi dòng một số n.
|Σ| ≤ 6, |R| ≤ 200, q ≤ 50, 0 ≤ n ≤ 18.
In q dòng, mỗi dòng là số chuỗi độ dài n khớp R.
Ví dụ:
Đầu vào:
ab
(a|b)*abb
3
3
4
5
Đầu ra:
1
2
4
Giải thích:
Đang tải editor...