We have a finite set of words D, and denote Pref(D) to be the set of all prefixes from words ofin 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)
↵
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)
