Synthesizing regular expressions from user-provided examples is a popular research area for programming by example (PBE) systems. Yet, synthesis from only positive examples remains an unsolved challenge due to a lack of a clear criterion to select the best solution and an infinite search space. Existing tools avoid this problem by requiring a wealth of additional information, such as negative examples or natural language descriptions. Our prior work Regex+ tackled the first challenge by introducing a pragmatic ranking function, which tripled the accuracy of existing neural and enumerative synthesizers on positive-example-only benchmarks. This paper builds upon Regex+, by addressing the second challenge of scalability. We introduce an admissible A* heuristic that relies on the prior ranking function, achieving a 90x decrease in memory usage and 1.9x speedup on a novel suite of benchmarks collected from a human study.