Research Online

Logo

Goldsmiths - University of London

Closed Factorization

Badkobeh, Golnaz; Bannai, Hideo; Goto, Keisuke; Inenaga, shunsuke; Sugimoto, Shiho; I, Tomohiro; Iliopoulos, Costas and Puglisi, Simon. 2016. Closed Factorization. Discrete Applied Mathematics, 212, pp. 23-29. ISSN 0166-218X [Article]

[img]
Preview
Text
closed.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial.

Download (307kB) | Preview

Abstract or Description

A closed string is a string with a proper substring that occurs in the string as a prefix and a suffix, but not elsewhere. Closed strings were introduced by Fici (Proc. WORDS, 2011) as objects of combinatorial interest in the study of Trapezoidal and Sturmian words. In this paper we present algorithms for computing closed factors (substrings) in strings. First, we consider the problem of greedily factorizing a string into a sequence of longest closed factors. We describe an algorithm for this problem that uses linear time and space. We then consider the related problem of computing, for every position in the string, the longest closed factor starting at that position. We describe a simple algorithm for the problem that runs in O(nlogn/loglogn) time, where n is the length of the string. This also leads to an algorithm to compute the maximal closed factor containing (i.e. covering) each position in the string in O(n log n/ log log n) time. We also present linear time algorithms to factorize a string into a sequence of shortest closed factors of length at least two, to compute the shortest closed factor of length at least two starting at each position of the string, and to compute a minimal closed factor of length at least two containing each position of the string.

Item Type:

Article

Identification Number (DOI):

https://doi.org/10.1016/j.dam.2016.04.009

Keywords:

closed strings, borders, suffix trees, range successor queries, Manhattan skyline problem

Departments, Centres and Research Units:

Computing

Dates:

DateEvent
16 April 2016Accepted
14 May 2016Published Online
30 October 2016Published

Item ID:

22714

Date Deposited:

09 Jan 2018 12:01

Last Modified:

11 Jul 2018 07:28

Peer Reviewed:

Yes, this version has been peer-reviewed.

URI:

http://research.gold.ac.uk/id/eprint/22714

View statistics for this item...

Edit Record Edit Record (login required)