Factorizing Strings into Repetitions

Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

A factorization f1,…,fm of a string w is called a repetition factorization of w if each factor fi is a repetition, namely, fi= xkx for some non-empty string x, an integer k ≥ 2, and x being a proper prefix of x. Dumitran et al. (Proc. SPIRE 2015) proposed an algorithm which computes an arbitrary repetition factorization of a given string w in O(n) time, where n is the length of w. 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 in O(nlogn) time, which respectively consist of the smallest/largest number of factors. The first algorithm is a simple O(nlogn) -space algorithm based on a reduction of the problem to the shortest/longest path problem on the DAG of size O(nlogn). The second one simulates the dynamic programming algorithm for shortest/longest path problem within O(n) space based on the idea of the first algorithm. Moreover, we discuss combinatorial structures of smallest/largest repetition factorizations of Fibonacci strings.

Original languageEnglish
JournalTheory of Computing Systems
DOIs
Publication statusAccepted/In press - 2022

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Factorizing Strings into Repetitions'. Together they form a unique fingerprint.

Cite this