2D Lyndon words and applications (Q513297): Difference between revisions

The words of the form \(uv\) and \(vu\) (where the latter word is the result of the right cyclic shift of the former word by \(\left| v\right| \) positions) are called conjugates. A Lyndon word is the unique word being minimal, with respect to the alphabetic ordering, among its conjugates. The uniqueness implies that a Lyndon word does not exist in the class of conjugates of a periodic word, i.e., of a word of the form \(u^{j}u^{\prime}\), where \(u^{\prime}\) is a proper prefix of \(u\) and \(j\geq2\). The authors propose a 2D version of Lyndon words based on properties of conjugates of rows of 2D words -- matrices of symbols. Two such matrices are horizontal conjugates if some right cyclic shift of columns of one of them leads to the other one. With each matrix they associate a column vector LWpos of integers where the entry in the \(i\)-th row is given as the smallest number of positions of a right cyclic shift of the \(i\)-th row leading to its minimal conjugate. Then a 2D Lyndon word is a horizontally non-periodic matrix, which yields the alphabetically minimal LWpos vector among all its horizontal conjugates. The paper introduces a simple algorithm for computing the 2D Lyndon word being a conjugate of a given matrix. As applications, linear time succinct (using asymptotically smaller space in addition to the input space) algorithms are given for the horizontal 2D all-pairs suffix-prefix matching problem and for the 2D dictionary matching problem. The horizontal 2D all-pairs suffix-prefix matching problem is to find, for any pair of matrices in a given set, the longest horizontal suffix of one which is a horizontal prefix of the other. The 2D dictionary matching problem is to find all occurrences of 2D patterns in a specified set, the dictionary, within a given 2D text.