Finding longest prefix of a given string in set of strings that satisies some property
I'll answer your generic question.  Store the RULES in a trie.  Then, you can generate each prefix of the QUERY, traversing the trie as you go.  This will let you enumerate all prefixes P of QUERY that are a member of RULES.  For each such prefix P, you can then evaluate F(P,QUERY).  The running time is $O(n)$ where $n$ is the length of QUERY, plus the time to do at most $n$ invocations of F.  If you want, you can check the longest prefixes of QUERY first, in order of decreasing length, so that once you find a single prefix P where F(P,QUERY) returns true, you can stop immediately.

I don't believe it is possible to do better, without knowing something about F.  Obviously, any algorithm must take at least $\Omega(n)$ time (since you must read each character of QUERY), and must invoke F potentially on each prefix that is a member of RULES.