In this paper we study the structure of suffix trees. Given an unlabeled tree @math on @math nodes and suffix links of its internal nodes, we ask the question "Is @math a suffix tree?", i.e., is there a string @math whose suffix tree has the same topological structure as @math ? We place no restrictions on @math , in particular we do not require that @math ends with a unique symbol. This corresponds to considering the more general definition of implicit or extended suffix trees. Such general suffix trees have many applications and are for example needed to allow efficient updates when suffix trees are built online. We prove that @math is a suffix tree if and only if it is realized by a string @math of length @math , and we give a linear-time algorithm for inferring @math when the first letter on each edge is known. This generalizes the work of [Discrete Appl. Math. 163, 2014].
The problem of revealing structural properties and exploiting them to recover a string realizing a data structure has received a lot of attention in the literature. Besides @math $-suffix trees, the problem has been considered for border arrays @cite_19 @cite_12 , parameterized border arrays @cite_8 @cite_0 @cite_9 , suffix arrays @cite_13 @cite_14 @cite_4 , KMP failure tables @cite_2 @cite_16 , prefix tables @cite_17 , cover arrays @cite_1 , directed acyclic word graphs @cite_13 , and directed acyclic subsequence graphs @cite_13 .
@cite_14 @cite_4 @cite_8 @cite_9 @cite_1 @cite_0 @cite_19 @cite_2 @cite_16 @cite_13 @cite_12 @cite_17
1589909894 2036743346 1834231399 1587287256 160379369 2162463605 1999151208 1874135322 56155448
The parameterized pattern matching problem is a kind of pattern matching problem, where a pattern is considered to occur in a text when there exists a renaming bijection on the alphabet with which the pattern can be transformed into a substring of the text. A parameterized border array (p-border array ) is an analogue of a border array of a standard string, which is also known as the failure function of the Morris-Pratt pattern matching algorithm. In this paper we present a linear time algorithm to verify if a given integer array is a valid p-border array for a binary alphabet. We also show a linear time algorithm to compute all binary parameterized strings sharing a given p-border array. In addition, we give an algorithm which computes all p-border arrays of length at most n , where n is a a given threshold. This algorithm runs in time linear in the number of output p-border arrays. The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array (p-border array) is a parameterized version of a standard border array, and we can efficiently solve the parameterized pattern matching problem using p-border arrays. In this paper, we present a linear time algorithm to verify if a given integer array is a valid p-border array for a binary alphabet. We also show a linear time algorithm to compute all binary parameterized strings sharing a given p-border array. In addition, we give an algorithm which computes all p-border arrays of length at most n, where n is a given threshold. This algorithm runs in O(B"2^n) time, where B"2^n is the number of all p-border arrays of length n for a binary parameter alphabet. The problems with a larger alphabet are much more difficult. Still, we present an O(n^1^.^5)-time O(n)-space algorithm to verify if a given integer array of length n is a valid p-border array for an unbounded alphabet. The best previously known solution to this task takes time proportional to the n-th Bell number [email protected]?"k"="0^ k^nk!, and hence our algorithm is much more efficient. Also, we show that it is possible to enumerate all p-border arrays of length at most n for an unbounded alphabet in O(B^nn^2^.^5) time, where B^n denotes the number of p-border arrays of length n. A proper factor u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimal-cover (resp. maximal-cover) array of y if C[i] is the minimal (resp. maximal) length of covers of y[0 . . i], or zero if no cover exists. In this paper, we present a constructive algorithm checking the validity of an array as a minimal-cover or maximal-cover array of some string. When the array is valid, the algorithm produces a string over an unbounded alphabet whose cover array is the input array. All algorithms run in linear time due to an interesting combinatorial property of cover arrays: the sum of important values in a cover array is bounded by twice the length of the string. The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array (p-border array) is a parameterized version of a standard border array, and we can efficiently solve the parameterized pattern matching problem using p-border arrays. In this paper we present an O(n1.5)-time O(n)-space algorithm to verify if a given integer array of length n is a valid p-border array for an unbounded alphabet. The best previously known solution takes time proportional to the n-th Bell number 1 eΣk=0∞kn k!, and hence our algorithm is quite efficient. A border of a string x is a proper (but possibly empty) prefix of x that is also a suffix of x. The border array β = β[1..n] of a string x = x[1..n] is an array of nonnegative integers in which each element β[i], 1 ≤ i ≤ n, is the length of the longest border of x[1..i]. In this paper we first present a simple linear-time algorithm to determine whether or not a given array y = y[1..n] of integers is a border array of some string on an alphabet of unbounded size. We state as an open problem the design of a corresponding and equally efficient algorithm on an alphabet of bounded size α. We then consider the problem of generating all possible distinct border arrays of given length n on a bounded or unbounded alphabet, and doing so in time proportional to the number of arrays generated. A previously published algorithm that claims to solve this problem in constant time per array generated is shown to be incorrect, and new algorithms are proposed. We state as open the design of an equally efficient on-line algorithm for this problem. We present an on-line linear time and space algorithm to check if an integer array f is the border array of at least one string w built on a bounded or unbounded size alphabet Σ . First of all, we show a bijection between the border array of a string w and the skeleton of the DFA recognizing Σ*ω, called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a skeleton of SMA is independent from the underlying strings. This enables to design algorithms for validating and generating border arrays that outperform existing ones. The validating algorithm lowers the delay (maximal number of comparisons on one element of the array) from O(|w|) to 1 + min |Σ|,1 + log 2 |ω| compared to existing algorithms. We then give results on the numbers of distinct border arrays depending on the alphabet size. We also present an algorithm that checks if a given directed unlabeled graph G is the skeleton of a SMA on an alphabet of size s in linear time. Along the process the algorithm can build one string w for which G is the SMA skeleton. Let @math 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 @math , is there a word w over an arbitrary alphabet Σ such that @math for all i? Moreover, what is the minimum cardinality of Σ required? We give an elementary and self-contained @math time algorithm for this problem, thus improving the previously known solution ( in Conference in honor of Donald E. Knuth, 2007), 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 @math . This paper introduces a new problem of inferring strings from graphs, and inferring strings from arrays. Given a graph G or an array A, we infer a string that suits the graph, or the array, under some condition. Firstly, we solve the problem of finding a string w such that the directed acyclic subsequence graph (DASG )o fw is isomorphic to a given graph G. Secondly, we consider directed acyclic word graphs (DAWGs) in terms of string inference. Finally, we consider the problem of finding a string w of a minimal size alphabet, such that the suffix array (SA )o f w is identical to a given permutation p = p1 ,...,p n of integers 1 ,...,n . Each of our three algorithms solving the above problems runs in linear time with respect to the input size. In this article we present an on-line linear time algorithm, to check if an integer array f is a border array of some string x built on a bounded size alphabet, which is simpler than the one given in [2]. Furthermore if f is a border array we are able to build, on-line and in linear time, a string x on a minimal size alphabet for which f is the border array. The reader can refer to the URL http: al.jalix.org Baba Applet to run the algorithm on his own examples.