Một nguyên nhân gây catastrophic backtracking trong động cơ regex kiểu duyệt lùi (backtracking) là khi một NFA có nhiều đường đi khác nhau cùng chấp nhận một xâu — động cơ phải thử lần lượt từng đường đi. Cho một NFA với ε-dịch chuyển (kí hiệu #), trong đó phần đồ thị chỉ gồm các cạnh ε không có chu trình (đảm bảo số đường đi hữu hạn), hãy đếm số đường đi chấp nhận phân biệt — tức số dãy dịch chuyển khác nhau xuất phát từ trạng thái 0, kết thúc ở một trạng thái kết thúc, mà các dịch chuyển mang kí tự (bỏ qua các dịch chuyển ε) ghép lại đúng bằng xâu truy vấn. Hai đường đi được coi là khác nhau nếu dãy cạnh (dịch chuyển) đã dùng khác nhau, kể cả khi hai dịch chuyển trùng nhau về (u,sym,v) nhưng được liệt kê ở hai dòng input khác nhau (do NFA không đơn định có thể có các cạnh song song). In kết quả theo modulo 109+7.
Dòng 1: ba số nguyên n m k — số trạng thái, số dịch chuyển, số truy vấn.
Dòng 2: số nguyên f rồi f chỉ số trạng thái kết thúc.
m dòng tiếp theo, mỗi dòng u sym v (sym là chữ cái thường hoặc # cho ε; phần đồ thị con chỉ gồm cạnh ε được đảm bảo không có chu trình).
k dòng tiếp theo, mỗi dòng một xâu truy vấn (xâu rỗng là @).
k dòng, mỗi dòng một số nguyên — số đường đi chấp nhận modulo 109+7 (in 0 nếu xâu không được chấp nhận theo đường đi nào).
Ví dụ: hai cạnh song song 0 a 1 (liệt kê hai lần) với trạng thái kết thúc {1}, xâu a cho kết quả 2.
Ví dụ:
Đầu vào:
4 4 2
1 3
0 # 1
0 # 2
1 a 3
2 a 3
a
@
Đầu ra:
2
0
Đầu vào:
2 2 2
1 1
0 a 1
0 a 1
a
@
Đầu ra:
2
0
Đang tải editor...