Cho biểu thức chính quy R dùng các phép: hợp |, nối (viết liền), lặp *, +, tùy chọn ?, nhóm () và ký tự đại diện . (khớp một ký tự bất kỳ). Kiểm tra chuỗi s có được R khớp toàn phần không.
Kỹ thuật gợi ý: dựng NFA (Thompson) rồi mô phỏng bằng bao đóng epsilon. Không dùng module re.
Ví dụ: a(b|c)*d khớp abccbd; a.c khớp axc.
Dòng 1: biểu thức R. Dòng 2: chuỗi s (có thể rỗng).
|R| ≤ 200, |s| ≤ 2000. R hợp lệ.
In KHOP nếu khớp toàn phần, ngược lại KHONG.
Ví dụ:
Đầu vào:
a(b|c)*d
abccbd
Đầu ra:
KHOP
Giải thích:
Đang tải editor...