Closed factorization

详细信息    查看全文

• 作者：Golnaz Badkobeh^a ; ^{g.badkobeh@sheffield.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Hideo Bannai^b ; ^{bannai@inf.kyushu-u.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Keisuke Goto^b ; ^{keisuke.gotou@inf.kyushu-u.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Tomohiro I^c ; ^{tomohiro.i@cs.tu-dortmund.de" class="auth_mail" title="E-mail the corresponding author} ; Costas S. Iliopoulos^d ; ^{c.iliopoulos@kcl.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Shunsuke Inenaga^b ; ^{inenaga@inf.kyushu-u.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Simon J. Puglisi^e ; ^{puglisi@cs.helsinki.fi" class="auth_mail" title="E-mail the corresponding author} ; Shiho Sugimoto^b ; ^{shiho.sugimoto@inf.kyushu-u.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Closed strings ; Borders ; Suffix trees ; Range successor queries ; Manhattan skyline problem
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 October 2016
• 年：2016
• 卷：212
• 期：Complete
• 页码：23-29
• 全文大小：431 K

文摘

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 (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 class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16301688&_mathId=si19.gif&_user=111111111&_pii=S0166218X16301688&_rdoc=1&_issn=0166218X&md5=16ac3573fa5468d30f890ef067d0c79d">class="imgLazyJSB inlineImage" height="15" width="130" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16301688-si19.gif">class="mathContainer hidden">class="mathCode">$O(nlogn/loglogn)$ time, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16301688&_mathId=si20.gif&_user=111111111&_pii=S0166218X16301688&_rdoc=1&_issn=0166218X&md5=15025f5ce6376bb7c307517c40b58643" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16301688&_mathId=si19.gif&_user=111111111&_pii=S0166218X16301688&_rdoc=1&_issn=0166218X&md5=16ac3573fa5468d30f890ef067d0c79d">class="imgLazyJSB inlineImage" height="15" width="130" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16301688-si19.gif">class="mathContainer hidden">class="mathCode">$O(nlogn/loglogn)$ 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.