We have a finite set of words D, and denote Pref(D) to be the set of all prefixes from words in D and l(D)=max|w| is the length of the longest word from D.

Problem statement: Given: D subset {0,1,...,sigma}* is finite set of words We will have queries of the following type: Input: u,v in Pref(D) Output: min{|a| | ua in D <=> va not in D}

How can we describe algorithm such that solves the problem and has the following: Time for indexing O(l(D)|Pref(D)|) Memory O(||Pref(D)) Time for answering a query O(1)