2D Lyndon words and applications (Q513297)

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.