solution

Cho biểu thức chính quy $p$ (theo đúng văn phạm ở bài "Động cơ regex bằng dựng NFA Thompson": chữ cái thường, |, *, nối tiếp ngầm định, dấu ngoặc ()). Gọi $\Sigma$ là tập các chữ cái thường xuất hiện trong $p$ — đây chính là bảng chữ cái hữu hạn của bài toán.

Cho một số nguyên $L$, hãy đếm số xâu độ dài đúng $L$ trên bảng chữ cái $\Sigma$ được $p$ khớp toàn bộ, lấy kết quả modulo $10^9+7$.

Gợi ý cách giải chuẩn: dựng NFA Thompson từ $p$, xác định hoá bằng dựng tập con để được DFA hữu hạn trạng thái, lập ma trận vuông $M$ với $M_{ij}$ là số ký hiệu của $\Sigma$ khiến DFA chuyển trực tiếp từ trạng thái $i$ sang trạng thái $j$, rồi dùng luỹ thừa ma trận nhanh ($O(\text{số trạng thái}^3 \log L)$) để tính $M^L$; đáp số là tổng các phần tử ở hàng ứng với trạng thái đầu, cột ứng với các trạng thái kết thúc của DFA.

Quy ước: nếu $p$ không chứa chữ cái nào (chỉ có thể khớp xâu rỗng $\varepsilon$), coi $\Sigma = \emptyset$; khi đó nếu $L=0$, đáp số là $1$ nếu $p$ khớp xâu rỗng và $0$ nếu không; nếu $L>0$, đáp số luôn là $0$.