Efficient algorithm for finding matching regular expressions given some text

Question

I have a large set (tens of thousands) of regular expressions defined by text and star symbol (matching subsequent characters 0 or more times). Given some text I would like to find the expression matching largest portion of that text, along with the subtext matched by the star symbol.

eg.

Patterns:
 Do you believe *
 What is *
 What is the meaning of *
 Where is * inn? 

Input:
 What is the meaning of life?

Output:
 What is the meaning of *
 life?

There must be some more efficient way of finding the right expression, other than exhaustive search. I've been looking into some means of indexing (directed graphs) but not sure how to avoid finding nonexistent expressions:

(what) - (is) - (inn)
(where) /   \ (the) - (meaning) ...

Where is the meaning...