On fast and memory-efficient construction of an antidictionary array
Hirotada Fukae, Takahiro Ota, Hiroyoshi Morita · 2012
An antidictionary, a set of words that never appear in a given string, is a useful data structure for source coding as well as other fields of computer sciences. A fast and memory-efficient algorithm for constructing antidictionaries by means of suffix array is presented. We prove that the proposed algorithm constructs an antidictionary array with linear time and space.