Abstract
In this dissertation, we study the text fingerprinting indexing problem, which was introduced by Amir et al. Let S be a string over a finite, ordered alphabet \Sigma. For any substring S' of S, the set of distinct characters contained in S' is called its fingerprint. The text fingerprinting indexing problem consists of constructing a data structure for the string S in advance, so that on given any input set C \subseteq \Sigma of characters, we can answer the following queries efficiently: (1) determine if C represents a fingerprint of some substrings in S; (2) find all maximal substrings of S whose fingerprint is equal to C. The best results known so far solved these two queries in □(|\Sigma|) and □(|\Sigma| + K) time, respectively, where K is the number of maximal substrings. In this dissertation, we propose two improved algorithms for the text fingerprinting indexing problem. The first algorithm solves the two queries in O(min{|C| log n, |\Sigma|}) and O(min{|C| log n, |\Sigma|} + K) time, respectively. The second algorithm solves them in O(|C| log (|\Sigma|/|C|)) and O(|C| log (|\Sigma|/|C|) + K) time, respectively, by using a new data structure with less storage than the existing solutions. Both results answer an open problem proposed by Amir et al.