Finding longest prefix of a given string in set of strings that satisies some property

Question

I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find longest prefix (lets call it P) of QUERY which is a member of RULES for which F(P,QUERY) returns true?

That was very generic definition of a problem. The reality is that I have a huge tree of objects. Each object has one of predefined types. I want to have a way to define different views on that tree. Each view is set of rules describing which types of objects are (in)visible in subtree subtree described by that rule. Basically a rule is a pair - path/prefix in tree and map from type to boolean. An object of type T is visible via given view iff the longest rule that has path that is prefix of that objects path has true as an entry for type T.

An example:

Types are {A,B,C}.

Tree contains those objects: /A1, /A2, /A1/B1, /A1/C1, /A1/B1/C1, /A2/B1, /A2/C1

View is defined by those rules: {/; C=>true, A=>true}, {/A1/B1; C=>true}, {/A1; C=>false}, {/A2; B=>true,C=>true}

Objects visible via that view: /A1, /A2, /A1/B1/C1, /A2/B1, /A2/C1

Right now I'm solving this by storing all rules for view in (hash)map - key is path and value is set of rules. When I've checking given object, I start from its full path and check in a loop each of is prefixes by removing top path component and looking it up in (hash)map. When it contains entry for that prefix I check if it contains entry for the type of object - if it does I return it as value of visibility. Otherwise I continue with next shorter prefix. If no rule was found I decide that object is not visible.

Answer 1

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.