2 papers
cs.DS2023
Linear-time computation of generalized minimal absent words for multiple strings
Kouta Okabe, Takuya Mieno, Yuto Nakashima +2
A string is called a minimal absent word (MAW) for a string if does not occur as a substring in and all proper substrings of occur in . MAWs are well-studied…
cs.DS2015
Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets
Yuto Nakashima, Tomohiro I, Shunsuke Inenaga +2
We present the first worst-case linear-time algorithm to compute the Lempel-Ziv 78 factorization of a given string over an integer alphabet. Our algorithm is based on nearest marke…