Factorizing Strings into Repetitions
Factorizing Strings into Repetitions
复制标题
将字符串分解为重复项
DOI：
10.1007/s00224-022-10070-3
复制
发表时间：
2022
影响因子：
0.5
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Hiroe Inoue;Yoshiaki Matsuoka;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
A因式分解f1，…如果一个串的每个因子都是一个重复，即对于某个非空串x，它是一个整数≥ 2，并且是一个适当的前缀，则称它为重复因子分解。Dumitran等人。(程序Spire 2015)提出了一个算法，该算法计算给定字符串O(N)时间的任意重复因式分解，其中是W的长度。他们的算法输出中包含的因素(即重复)的数量是未知的或不能保证的。本文提出了两种在时间上计算最小/最大重复因式分解的算法，它们分别由最小/最大因数组成。第一种算法是一种简单空间算法，基于将问题归结为大小为DAG上的最短/最长路径问题。第二种算法基于动态规划算法的思想，模拟求解O(N)空间内最短/最长路径问题的动态规划算法。此外，我们还讨论了Fibonacci弦的最小/最大重复因式分解的组合结构。
A factorizationf1,…,fmof a stringwis called arepetition factorizationofwif each factorfiis a repetition, namely,for some non-empty stringx, an integerk≥ 2, andbeing a proper prefix ofx. Dumitran et al. (Proc. SPIRE 2015) proposed an algorithm which computes an arbitrary repetition factorization of a given stringwinO(n) time, wherenis the length ofw. The number of factors (i.e. repetitions) contained in the output of their algorithm is not known or guaranteed. In this paper, we propose two algorithms for computing smallest/largest repetition factorizations intime, which respectively consist of the smallest/largest number of factors. The first algorithm is a simple-space algorithm based on a reduction of the problem to the shortest/longest path problem on the DAG of size. The second one simulates the dynamic programming algorithm for shortest/longest path problem withinO(n) space based on the idea of the first algorithm. Moreover, we discuss combinatorial structures of smallest/largest repetition factorizations of Fibonacci strings.
登录
查看更多内容
论前缀/后缀平方自由词
DOI：
--
发表时间：
2015
期刊：
SPIRE
影响因子：
--
作者：
Marius Dumitran;F. Manea;Dirk Nowotka
通讯作者：
Dirk Nowotka
搜索单词中的间隙重复和子重复
DOI：
--
发表时间：
2013
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
R. Kolpakov;Mikhail Podolskiy;M. Posypkin;Nickolay Khrapov
通讯作者：
Nickolay Khrapov
平方、立方体和时空有效的字符串搜索
影响因子：
1.1
作者：
M. Crochemore;W. Rytter
通讯作者：
W. Rytter
关于 Burrows-Wheeler 变换的双射变体
DOI：
--
发表时间：
2009
期刊：
Prague Stringology Conference
影响因子：
--
作者：
Manfred Kufleitner
通讯作者：
Manfred Kufleitner
线性时间运行于一般有序字母表上
DOI：
10.4230/lipics.icalp.2021.63
发表时间：
2021
期刊：
The New England journal of medicine
影响因子：
--
作者：
J. Ellert;J. Fischer
通讯作者：
J. Fischer