Minimal Unique Substrings and Minimal Absent Words in a Sliding Window

DOI10.1007/978-3-030-38919-2_13MaRDI QIDQ3297764zbMATH OpenOpenAlexFDO

Authors Takuya Mieno, Yuki Kuhara, Tooru Akagi, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date 20 July 2020

Published in SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.02804

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: A substring $u$ of a string $T$ is called a minimal unique substring (MUS) of $T$ if $u$ occurs exactly once in $T$ and any proper substring of $u$ occurs at least twice in $T$. A string $w$ is called a minimal absent word (MAW) of $T$ if $w$ does not occur in $T$ and any proper substring of $w$ occurs in $T$. In this paper, we study the problems of computing MUSs and MAWs in a sliding window over a given string $T$. We first show how the set of MUSs can change in a sliding window over $T$, and present an $O(nlogsigma)$-time and $O(d)$-space algorithm to compute MUSs in a sliding window of width $d$ over $T$, where $sigma$ is 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 over $T$. Our bounds improve on the previous results in [Crochemore et al., 2017].

Recommendations

• Computing minimal unique substrings for a sliding window
• Minimal absent words in a sliding window and applications to on-line pattern matching
• Combinatorics of minimal absent words for a sliding window
• Minimum unique substrings and maximum repeats
• Absent words in a sliding window with applications
• Minimizing positive integer sequences without duplicate substrings
• Tight bounds on the maximum number of shortest unique substrings
• On minimal words with given subword complexity
• Space-efficient algorithms for computing minimal/shortest unique substrings
• Further results on minimizing positive integer sequences without duplicate substrings

Cites work

• A universal algorithm for sequential data compression
• Dynamic construction of an antidictionary with linear complexity
• Minimal absent words in a sliding window and applications to on-line pattern matching
• On-line construction of suffix trees
• Shortest Unique Substring Queries on Run-Length Encoded Strings
• Shortest unique substrings queries in optimal time
• Using minimal absent words to build phylogeny

Cited in

(10)

• Computing minimal unique substrings for a sliding window
• Combinatorics of minimal absent words for a sliding window
• Palindromic trees for a sliding window and its applications
• Absent words in a sliding window with applications
• Internal shortest absent word queries in constant time and linear space
• Absent subsequences in words
• Reverse-safe text indexing
• Absent Subsequences in Words
• Linear-time computation of generalized minimal absent words for multiple strings
• Double-ended palindromic trees in linear time

This page was built for publication: Minimal Unique Substrings and Minimal Absent Words in a Sliding Window

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297764)