hide
Free keywords:
-
Abstract:
Let π'_w denote the failure function of the Knuth-Morris-Pratt algorithm
for a word w.
In this paper we study the following problem: given an integer array A'[1 ..
n], is there
a word w over an arbitrary alphabet Σ such that A'[i]=π'_w[i] for
all i?
Moreover, what is the minimum cardinality of Σ required?
We give an elementary and self-contained \mathcalO}(nłog n) time algorithm
for this problem,
thus improving the previously known solution, which had no polynomial time
bound.
Using both deeper combinatorial insight into the structure of π' and
advanced algorithmic
tools, we further improve the running time to \mathcal{O(n).
