Minimal unique substrings and minimal absent words in a sliding window
Minimal unique substrings and minimal absent words in a sliding window
复制标题
滑动窗口中最少的唯一子串和最少的缺失单词
DOI：
10.1007/978-3-030-38919-2_13
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Takuya Mieno;Yuki Kuhara;Tooru Akagi;Yuta Fujishige;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
字符串的子串称为最小唯一子串 (MUS)，Tifu 在 T 中恰好出现一次，并且任何真子串在 T 中至少出现两次。称为 Tifw 的最小缺失词 (MAW) 的字符串不会出现在 T 中，并且 w 的任何真子串会出现在 T 中。在本文中，我们研究了在给定 stringT 上的滑动窗口中计算 MUS 和 MAW 的问题。我们首先展示了 MUS 集合如何在 T 上的滑动窗口中变化，并提出一个时间和 O(d) 空间算法来计算 widthdoverT 的滑动窗口中的 MUS，其中是每个窗口中不同字符的最大数量。然后，我们对 T 上的滑动窗口中 MAW 集合的最大变化数给出严格的上限和下限。我们的界限改进了 Crochemore 等人之前的结果。 （2017）。
A substringuof a stringTis called a minimal unique substring (MUS) ofTifuoccurs exactly once inTand any proper substring ofuoccurs at least twice inT. A stringwis called a minimal absent word (MAW) ofTifwdoes not occur inTand any proper substring ofwoccurs inT. In this paper, we study the problems of computing MUSs and MAWs in a sliding window over a given stringT. We first show how the set of MUSs can change in a sliding window overT, and present an-time andO(d)-space algorithm to compute MUSs in a sliding window of widthdoverT, whereis the maximum number of distinct characters in every window. We then give tight upper and lower bounds on the maximum number of changes in the set of MAWs in a sliding window overT. Our bounds improve on the previous results in Crochemore et al. (2017).