2023/07/05 by Okabe, Kouta, Mieno, Takuya, Nakashima, Yuto +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2307.01967
A string w is called a minimal absent word (MAW) for a string S if w does not occur as a substring in S and all proper substrings of w occur in S. MAWs are well-studied combinatorial string objects that have potential applications in areas including bioinformatics, musicology, and data compression. In this paper, we generalize the notion of MAWs to a set S = \S1, …, Sk\ of multiple strings. We first describe our solution to the case of k = 2 strings, and show how to compute the set M of MAWs in optimal O(n + |M|) time and with O(n) working space, where n denotes the total length of the strings in S. We then move on to the general case of k > 2 strings, and show how to compute the set M of MAWs in O(n \lceil k / log n \rceil + |M|) time and with O(n (k + log n)) bits of working space, in the word RAM model with machine word size ω= log n. The latter algorithm runs in optimal O(n + |M|) time for k = O(log n).