Before revision:  Our findings imply that in polynomial time  we can build an index breaking the worst-case conditional lower bound of \Omega( \pi m), whenever the input NFA's width is at most \epsilon \log_2 m, for any constant 0 \leq \epsilon < 1/2.
After revision:  Our findings imply that in polynomial time we can build an index breaking the worst-case conditional lower bound of \Omega( |P| m), whenever the input NFA's width is at most \epsilon \log_2 m, for any constant 0 \leq \epsilon < 1/2.