Yup, the most resource constrained form (PCRE2 would be the Cadillac-DoS-my-webapp option). I don't know how abnormal my problem is, but I've run into several cases where I needed a file that had a very specific naming structure - but a couple of substrings needed to be masked because that was the information I was looking for. That can easily be handled with two fixed string passes on a local file system, but not so much at the scale we're talking here.
As far as the indexing issues you mentioned, I'm not a python guy, so I can't recommend a drop in solution. But I have indexed pretty massive string datasets, and you definitely want to select an index method that was specifically devised for the key/value datatype you intend to ingest. So hashmaps are probably out :) It would also pay to adapt either the implementation or the data itself. For example, say you had a bunch of font file name you wanted to index (XyzSans.otf, AsdfSans.otf, AsdfSerif.otf, etc): a prefix tree would be a pretty good fit, especially if you reversed all the strings.