Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 4 февраля 2014 г.
Аннотация:Let s=s1..sn be a text (or sequence) on a finite alphabet Σ. A fingerprint in s is the set of distinct characters contained in one of its substrings. Fingerprinting a text consists of computing the set F of all fingerprints of all its substrings and being able to efficiently answer several questions on this set. A given fingerprint f∈F is represented by a binary array, F, of size |Σ| named a fingerprint table. A fingerprint, f∈F, admits a number of maximal locations [i..j] in S, that is the alphabet of si..sj is f and si−1,sj+1, if defined, are not in f. The set of maximal locations is View the MathML source. We present new algorithms and a new data structure for the three problems: (1) compute F; (2) given F, answer if F represents a fingerprint in F; (3) given F, find all maximal locations of F in s. These problems are, respectively, solved in O(n+|L|log|Σ|), Θ(|Σ|), and Θ(|Σ|+K) time—where K is the number of maximal locations of F.