TY - GEN
T1 - Closed factorization
AU - Badkobeh, Golnaz
AU - Bannai, Hideo
AU - Goto, Keisuke
AU - I, Tomohiro
AU - Iliopoulos, Costas S.
AU - Inenaga, Shunsuke
AU - Puglisi, Simon J.
AU - Sugimoto, Shiho
N1 - Funding Information:
This research is partially supported by the Academy of Finland through grants 258308 and by the Japan Society for the Promotion of Science .
Publisher Copyright:
© Czech Technical University in Prague, Czech Republic.
PY - 2014
Y1 - 2014
N2 - 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 consider algorithms for computing closed factors (substrings) in strings, and in particular for 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(n log n/ log log n) time.
AB - 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 consider algorithms for computing closed factors (substrings) in strings, and in particular for 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(n log n/ log log n) time.
UR - http://www.scopus.com/inward/record.url?scp=84928791807&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84928791807&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84928791807
T3 - Proceedings of the Prague Stringology Conference 2014, PSC 2014
SP - 162
EP - 168
BT - Proceedings of the Prague Stringology Conference 2014, PSC 2014
A2 - Holub, Jan
A2 - Zd'arek, Jan
PB - Prague Stringology Club
T2 - 18th Prague Stringology Conference, PSC 2014
Y2 - 1 September 2014 through 3 September 2014
ER -