  The suffix array, perhaps the most important data structure in modern string
processing, is often augmented with the longest common prefix (LCP) array which
stores the lengths of the LCPs for lexicographically adjacent suffixes of a
string. Together the two arrays are roughly equivalent to the suffix tree with
the LCP array representing the tree shape.
  In order to better understand the combinatorics of LCP arrays, we consider
the problem of inferring a string from an LCP array, i.e., determining whether
a given array of integers is a valid LCP array, and if it is, reconstructing
some string or all strings with that LCP array. There are recent studies of
inferring a string from a suffix tree shape but using significantly more
information (in the form of suffix links) than is available in the LCP array.
  We provide two main results. (1) We describe two algorithms for inferring
strings from an LCP array when we allow a generalized form of LCP array defined
for a multiset of cyclic strings: a linear time algorithm for binary alphabet
and a general algorithm with polynomial time complexity for a constant alphabet
size. (2) We prove that determining whether a given integer array is a valid
LCP array is NP-complete when we require more restricted forms of LCP array
defined for a single cyclic or non-cyclic string or a multiset of non-cyclic
strings. The result holds whether or not the alphabet is restricted to be
binary. In combination, the two results show that the generalized form of LCP
array for a multiset of cyclic strings is fundamentally different from the
other more restricted forms.
