hard queries problem — algorithm

Revision en2, by andy4889, 2020-12-04 13:31:57

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)

Tags queries, sufix, prefix, automata


  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)