Unfortunately this is not currently possible in MultiChain.
In the next week we're scheduled to release the first preview / alpha version of MultiChain 2.0, which will include the ability to assign multiple keys to stream items. This will give you a good workaround for this kind of pattern matching requirement, so long as you know what sort of searches you are going to do ahead of time. In your example you would assign keys to the above examples as follows:
Then you could retrieve all items with _prefix_p to do your matching based on the first character. Of course, this is still not as good as a full regular expression matching engine.