Minimal Unique Substrings and Minimal Absent Words in a Sliding Window

09/06/2019
by   Takuya Mieno, et al.
0

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(nσ)-time and O(d)-space algorithm to compute MUSs in a sliding window of width d over T, where σ 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].

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset