Closed factorization
作者： Golnaz Badkobeh , Hideo Bannai , Keisuke Goto , Tomohiro I , Costas S. Iliopoulos
DOI: 10.1016/J.DAM.2016.04.009
关键词: Space (mathematics) 、 Combinatorics 、 SIMPLE algorithm 、 Factorization 、 String (computer science) 、 Mathematics 、 Substring 、 Time complexity 、 Sequence 、 Position (vector)
摘要: A closed string is a with proper substring that occurs in the as prefix and suffix, but not elsewhere. Closed strings were introduced by Fici (2011) objects of combinatorial interest study Trapezoidal Sturmian words. In this paper we present algorithms for computing factors (substrings) strings. First, consider problem greedily factorizing into sequence longest factors. We describe an algorithm uses linear time space. then related computing, every position string, factor starting at position. simple runs O ( n log / ) time, where length string. This also leads to compute maximal containing (i.e.źcovering) each time. factorize shortest least two, two minimal
acm.org 
sci-hub.se 参考文章(10)
Yakov Nekrich, Gonzalo Navarro, Sorted range reporting scandinavian workshop on algorithm theory. pp. 271- 282 ,(2012) , 10.1007/978-3-642-31155-0_24
Donald E Knuth, James H Morris, Jr, Vaughan R Pratt, Fast Pattern Matching in Strings SIAM Journal on Computing. ,vol. 6, pp. 323- 350 ,(1977) , 10.1137/0206024
Chih-Chiang Yu, Wing-Kai Hon, Biing-Feng Wang, Improved data structures for the orthogonal range successor problem Computational Geometry. ,vol. 44, pp. 148- 159 ,(2011) , 10.1016/J.COMGEO.2010.09.001
Maxime Crochemore, Costas S Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Extracting powers and periods in a word from its runs structure Theoretical Computer Science. ,vol. 521, pp. 29- 41 ,(2014) , 10.1016/J.TCS.2013.11.018
M. Farach, Optimal suffix tree construction with large alphabets foundations of computer science. pp. 137- 143 ,(1997) , 10.1109/SFCS.1997.646102
Udi Manber, Gene Myers, Suffix Arrays: A New Method for On-Line String Searches SIAM Journal on Computing. ,vol. 22, pp. 935- 948 ,(1993) , 10.1137/0222058
Golnaz Badkobeh, Gabriele Fici, Zsuzsanna Lipták, A Note on Words With the Smallest Number of Closed Factors ,(2013)
Peter Weiner, Linear pattern matching algorithms 14th Annual Symposium on Switching and Automata Theory (swat 1973). pp. 1- 11 ,(1973) , 10.1109/SWAT.1973.13
Gabriele Fici, A Classification of Trapezoidal Words Electronic Proceedings in Theoretical Computer Science. ,vol. 63, pp. 129- 137 ,(2011) , 10.4204/EPTCS.63.18
Gabriele Fici, A Classification of Trapezoidal Words arXiv: Formal Languages and Automata Theory. ,(2011) , 10.4204/EPTCS.63.18