Inferring strings from Lyndon factorization
Inferring strings from Lyndon factorization
复制标题
DOI：
10.1016/j.tcs.2017.05.038
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Yuto Nakashima;T. Okabe;T. I.;Shunsuke Inenaga;H. Bannai;M. Takeda
中科院分区：
文献类型：
--
作者：
Yuto Nakashima;T. Okabe;T. I.;Shunsuke Inenaga;H. Bannai;M. Takeda
串w的Lyndon分解是唯一的分解ℓ1 p 1，…，ℓm p m of w使得ℓ1，…，ℓm是按词典顺序单调递减的林登词序列。本文考虑了关于Lyndon分解的逆工程问题：给定一个序列S=((S 1，p1)，…，(S m，pm))的正整数序对，找出其林登分解对应于输入序列S的串w，即w的林登分解为ℓ1 p1，…，ℓm pm其中|ℓi|=S i对于所有的1≤i≤m。首先，我们证明了如果字母表的大小是无界的，则存在一个简单的O(N)时间算法，其中n是输出串的长度。其次，我们提出了一个O(N)次的算法来计算最小字母表上的字符串。第三，我们展示了如何在O(M)时间内只计算最小字母表的大小。第四，我们给出了一个O(M)时间算法来计算最小字母表上的一个字符串的O(M)大小表示。最后，我们提出了一个有效的算法来枚举其Lyndon分解对应于S的所有字符串。
The Lyndon factorization of a string w is a unique factorization ℓ 1 p 1,…, ℓ m p m of w such that ℓ 1,…, ℓ m is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization: Given a sequence S=((s 1, p 1),…,(s m, p m)) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S, ie, the Lyndon factorization of w is in a form of ℓ 1 p 1,…, ℓ m p m with| ℓ i|= s i for all 1≤ i≤ m. Firstly, we show that there exists a simple O (n)-time algorithm if the size of the alphabet is unbounded, where n is the length of the output string. Secondly, we present an O (n)-time algorithm to compute a string over an alphabet of the smallest size. Thirdly, we show how to compute only the size of the smallest alphabet in O (m) time. Fourthly, we give an O (m)-time algorithm to compute an O (m)-size representation of a string over an alphabet of the smallest size. Finally, we propose an efficient algorithm to enumerate all strings whose Lyndon factorizations correspond to S.