hard queries problem - algorithm
Difference between en1 and en2, changed 6 character(s)
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)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English andy4889 2020-12-04 13:31:57 6 Tiny change: 'rom words of D and l(D' -> 'rom words in D and l(D'
en1 English andy4889 2020-12-04 13:31:10 555 Initial revision (published)