TY - GEN
T1 - Efficient algorithms for longest closed factor array
AU - Bannai, Hideo
AU - Inenaga, Shunsuke
AU - Kociumaka, Tomasz
AU - Lefebvre, Arnaud
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Sugimoto, Shiho
AU - Waleń, Tomasz
N1 - Funding Information:
W. Rytter—Supported by the Polish National Science Center, grant no 2014/13/B/ST6/00770.
Funding Information:
J. Radoszewski—Receives financial support of Foundation for Polish Science.
Funding Information:
J. Radoszewski and T. Waleń—Supported by the Polish Ministry of Science and Higher Education under the ‘Iuventus Plus’ program in 2015-2016 grant no 0392/IP3/2015/73.
Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - We consider a family of strings called closed strings and a related array of Longest Closed Factors (LCF). We show that the reconstruction of a string from its LCF array is easier than the construction and verification of this array. Moreover, the reconstructed string is unique. We improve also the time of construction/verification, reducing it from (image found) (n log n/ log log n) (the best previously known) to (image found) (n √log n).We use connections between the LCF array and the longest previous/next factor arrays.
AB - We consider a family of strings called closed strings and a related array of Longest Closed Factors (LCF). We show that the reconstruction of a string from its LCF array is easier than the construction and verification of this array. Moreover, the reconstructed string is unique. We improve also the time of construction/verification, reducing it from (image found) (n log n/ log log n) (the best previously known) to (image found) (n √log n).We use connections between the LCF array and the longest previous/next factor arrays.
UR - http://www.scopus.com/inward/record.url?scp=84944699362&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84944699362&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-23826-5_10
DO - 10.1007/978-3-319-23826-5_10
M3 - Conference contribution
AN - SCOPUS:84944699362
SN - 9783319238258
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 95
EP - 102
BT - String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings
A2 - Puglisi, Simon J.
A2 - Iliopoulos, Costas S.
A2 - Yilmaz, Emine
PB - Springer Verlag
T2 - 22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015
Y2 - 1 September 2015 through 4 September 2015
ER -