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

    solution

    Đề bài: [Trình biên dịch] Khớp regex bằng đạo hàm Brzozowski

    Đạo hàm Brzozowski (Brzozowski derivative) là một kĩ thuật cài đặt động cơ regex không cần dựng NFA tường minh: đạo hàm Dc(r)D_c(r)Dc​(r) của biểu thức rrr theo kí tự ccc mô tả phần ngôn ngữ còn lại sau khi đã "nuốt" kí tự ccc; xâu w=c1c2…cnw=c_1c_2\dots c_nw=c1​c2​…cn​ khớp toàn phần rrr khi và chỉ khi biểu thức Dcn(…Dc1(r))D_{c_n}(\dots D_{c_1}(r))Dcn​​(…Dc1​​(r)) là nullable (chấp nhận xâu rỗng). Cho biểu thức chính quy rrr theo văn phạm:

    • kí tự thường a-z là kí tự đơn;
    • nối tiếp bằng cách viết liền nhau (không cần dấu .), ví dụ ab là aaa nối bbb;
    • | là toán tử hội;
    • * (hậu tố) là lặp Kleene;
    • ( ) để nhóm.

    Với mỗi xâu truy vấn, hãy xác định xâu đó có khớp toàn bộ (từ đầu đến cuối) biểu thức rrr hay không.

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

      Dòng 1: biểu thức chính quy rrr (không khoảng trắng, độ dài ≤60\le 60≤60, hợp lệ theo văn phạm trên). Dòng 2: số nguyên kkk — số xâu truy vấn. kkk dòng tiếp theo, mỗi dòng một xâu chữ cái thường cần kiểm tra (xâu rỗng biểu diễn bằng @).

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

      kkk dòng, mỗi dòng ACCEPT hoặc REJECT.

      Ví dụ: r=r=r= a(b|c)*d, xâu abcbd cho kết quả ACCEPT.

    Ví dụ:

    Đầu vào:

    a(b|c)*d
5
ad
abcbd
a
abd
abce

    Đầu ra:

    ACCEPT
ACCEPT
REJECT
ACCEPT
REJECT

    Đầu vào:

    (a|b)(a|b)
5
aa
ab
ba
a
abc

    Đầu ra:

    ACCEPT
ACCEPT
ACCEPT
REJECT
REJECT

    Đang tải editor...