Space-efficient algorithms for computing minimal/shortest unique substrings
Space-efficient algorithms for computing minimal/shortest unique substrings
复制标题
DOI：
10.1016/j.tcs.2020.09.017
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Takuya Mieno;D. Köppl;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda
中科院分区：
文献类型：
--
作者：
Takuya Mieno;D. Köppl;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda
给定一个长度为n的字符串T，一个子串u=T[i.如果(A)u在T中恰好出现一次，(B)u包含区间[S，t](即i≤S≤t≤j)，以及(C)T的每个具有|v|<；|u|包含[S，t]的子串v在T中至少出现两次，则称为区间[S，t]的最短唯一子串(SUS)。给定查询区间[S，t]⊂[1，n]，区间SUS问题是输出区间[S，t]的所有SU。本文提出了一种4n+o(N)比特的数据结构，该结构在对输出敏感的O(Oc C)时间内回答间隔SUS查询，其中OCC是返回的SUS的数目。此外，我们还研究了点SUS问题，即S=t的区间SUS问题。在这里，我们提出了一种⌈(log23+1)n⌉+o(N)bit的数据结构，在相同的输出敏感时间内回答一个点SUS查询。给出了计算T的最小唯一子串的空间效率算法。
Given a string T of length n, a substring u= T [i.. j] of T is called a shortest unique substring (SUS) for an interval [s, t] if (a) u occurs exactly once in T,(b) u contains the interval [s, t](ie i≤ s≤ t≤ j), and (c) every substring v of T with| v|<| u| containing [s, t] occurs at least twice in T. Given a query interval [s, t]⊂[1, n], the interval SUS problem is to output all the SUSs for the interval [s, t]. In this article, we propose a 4 n+ o (n) bits data structure answering an interval SUS query in output-sensitive O (o c c) time, where occ is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for s= t. Here, we propose a⌈(log 2 3+ 1) n⌉+ o (n) bits data structure answering a point SUS query in the same output-sensitive time. We also propose space-efficient algorithms for computing the minimal unique substrings of T.