  Let pi_w denote the failure function of the 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 arbitrary alphabet such that A[i]=pi_w[i] for
all i? Moreover, what is the minimum required cardinality of the alphabet? We
give a real time linear algorithm for this problem in the unit-cost RAM model
with \Theta(log n) bits word size. Our algorithm returns a word w over minimal
alphabet such that pi_w = A as well and uses just o(n) words of memory. Then we
consider function pi' instead of pi and give an online O(n log n) algorithm for
this case. This is the first polynomial algorithm for online version of this
problem.
