Actually that isn't made explicitly clear in the original post, although I agree the absence of anchors certainly indicates that you're correct.

Tie::Hash::Regex would work in that case, but unfortunately all the efficiency of the hash would be lost as that module simply iterates over the keys in the hash doing a regex match :^\