Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Automat & NN hình thức] Đếm chuỗi độ dài n khớp

    Cho bảng chữ Σ, biểu thức chính quy R và số nguyên n. Đếm số chuỗi có độ dài đúng bằng n trên Σ thuộc L(R).

    Gợi ý: xây DFA rồi quy hoạch động theo độ dài.

    Ví dụ: Σ={a,b}, R=(a|b)*, n=2 → 4; R=a*, n=3 → 1.

    • Định dạng đầu vào:

      Dòng 1: Σ. Dòng 2: R. Dòng 3: n.

    • Ràng buộc đầu vào:

      |Σ| ≤ 10, |R| ≤ 200, 0 ≤ n ≤ 15.

    • Định dạng đầu ra:

      In số lượng chuỗi độ dài n khớp R.

    Ví dụ:

    Đầu vào:

    ab
(a|b)*
2

    Đầu ra:

    4

    Giải thích:

    Mọi chuỗi độ dài 2 trên {a,b}: aa,ab,ba,bb → 4.

    Đang tải editor...