Có các mẫu bệnh lý Lua với thời gian chạy theo cấp số nhân không?

Question

Được biết rằng các cụm từ thông dụng được thực hiện theo kiểu đệ quy (thay vì NFA/DFA) có thể cần trong một số trường hợp thời gian chạy theo hàm mũ. Các mẫu Lua được thực hiện thông qua một trình kết hợp đệ quy (chúng cho phép backtracking), nhưng chúng ít mạnh hơn các biểu thức thông thường (quên mẫu% b).

Mẫu Lua có thể cần thời gian chạy theo hàm mũ không? Và không có backtracking (bất kỳ sự xuất hiện của% 0,% 1,% 2 ... pattern)? Nếu vậy, tôi sẽ đánh giá cao một số ví dụ.

Answer 1

Có, các mẫu lua có thể mất thời gian theo cấp số nhân. Thử chạy:

string.find('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 
    'a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?' 
    .. 'a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa') 

Họ vẫn có thể chạy khá nhanh nếu bạn giữ cho mô hình đơn giản mặc dù vậy tôi sẽ cố gắng thử nghiệm một số ví dụ thực tế về dữ liệu của riêng bạn.