Computing minimal and maximal suffixes of a substring

详细信息    查看全文

• 作者：Maxim Babenko^a ; ^{maxim.babenko@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Paweł Gawrychowski^b ; ¹ ; ^{gawry@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Tomasz Kociumaka^b ; ² ; ^{kociumaka@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Ignat Kolesnichenko^c ; ^{ignat@yandex-team.ru" class="auth_mail" title="E-mail the corresponding author} ; Tatiana Starikovskaya^d ; ^{tat.starikovskaya@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Data structures ; Substring queries ; Lexicographic order ; Minimal suffix ; Maximal suffix
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：25 July 2016
• 年：2016
• 卷：638
• 期：Complete
• 页码：112-121
• 全文大小：420 K

文摘

We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length n. For the minimal suffix problem we show that for every τ  , class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007707&_mathId=si1.gif&_user=111111111&_pii=S0304397515007707&_rdoc=1&_issn=03043975&md5=5d64ac19b4cd1d3f88bd4e4e8774d35f" title="Click to view the MathML source">1≤τ≤log⁡nclass="mathContainer hidden">class="mathCode">$1\le \tau \le \log n$, there exists a linear-space data structure with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007707&_mathId=si165.gif&_user=111111111&_pii=S0304397515007707&_rdoc=1&_issn=03043975&md5=eee79641ba67e852bf01e7886bdb9ded" title="Click to view the MathML source">O(τ)class="mathContainer hidden">class="mathCode">$\mathcal{O}(\tau )$ query time and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007707&_mathId=si166.gif&_user=111111111&_pii=S0304397515007707&_rdoc=1&_issn=03043975&md5=e9262a4d9a1fc19afe0f678ab9f67dff" title="Click to view the MathML source">O(nlog⁡n/τ)class="mathContainer hidden">class="mathCode">$\mathcal{O}(n\log n/\tau )$ preprocessing time. As a sample application, we show that this data structure can be used to compute the Lyndon decomposition of any substring of the text in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007707&_mathId=si172.gif&_user=111111111&_pii=S0304397515007707&_rdoc=1&_issn=03043975&md5=842d5c13a6a2eb08a31eb7d6f37f321b" title="Click to view the MathML source">O(kτ)class="mathContainer hidden">class="mathCode">$\mathcal{O}(k\tau )$ time, where k   is the number of distinct factors in the decomposition. For the maximal suffix problem, we give a linear-space structure with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007707&_mathId=si112.gif&_user=111111111&_pii=S0304397515007707&_rdoc=1&_issn=03043975&md5=462f75d0ecffd60e935ce468633554af" title="Click to view the MathML source">O(1)class="mathContainer hidden">class="mathCode">$\mathcal{O}(1)$ query time and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515007707&_mathId=si119.gif&_user=111111111&_pii=S0304397515007707&_rdoc=1&_issn=03043975&md5=9e85e4ea384018afb41c8d6f338b1ea2" title="Click to view the MathML source">O(n)class="mathContainer hidden">class="mathCode">$\mathcal{O}(n)$ preprocessing time. In other words, we simultaneously achieve both the optimal query time and the optimal construction time.