andy4889's blog

By andy4889, history, 6 weeks ago, In English

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)

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by andy4889 (previous revision, new revision, compare).