Prefix Arrays, Indeterminate Strings, and Partial Words


Best Ever. paper abstract app app app app app F. Blanchet-Sadri F. Blanchet-Sadri F. Blanchet-Sadri F. Blanchet-Sadri F. Blanchet-Sadri

Abstract

We explore prefix arrays of indeterminate strings and partial words. If prefix array \(y\) is the prefix array for indeterminate string \(w\), then we say \(w\) satisfies \(y\). We use a graph theoretic approach to find a string on a minimum alphabet size which satisfies a given prefix array. We relate the problem of finding a minimum alphabet size to finding edge clique covers of a particular graph, allowing us to bound the minimum alphabet size by \(n + \sqrt{n}\) for indeterminate strings, where \(n\) is the length of the prefix array. When we restrict ourselves to prefix arrays for partial words, we are able to bound the minimum alphabet size by \(\Big\lceil \sqrt{2n} \Big\rceil\). Moreover, we show that this bound is tight up to a constant multiple by using Sidon sets.

We also study the relationship between border arrays and prefix arrays for partial words. We give necessary and sufficient conditions for a border array and prefix array to be satisfied by the same word, and we give an algorithm to enumerate all prefix arrays for partial words of a given length, \(n\). This algorithm has a time complexity of \(n^2\) times the output size, that is the number of valid prefix arrays for partial words of length \(n\).