New algorithms for text fingerprinting
Let s=s1..sn s = s 1 . . s n 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 F of all fingerprints of all its substrings and being able to efficiently answer several questions on this set. A given fingerprint f?F f ? F is represented by a binary array, F , of size |?| | ? | named a fingerprint table. A fingerprint, f?F f ? F , admits a number of maximal locations ?i,j? ? i , j ? in S , that is the alphabet of si..sj s i . . s j is f  and si?1,sj+1 s i ? 1 , s j + 1 , if defined, are not in f . The set of maximal locations is L , | L | ? n | ? | . We present new algorithms and a new data structure for the three problems: (1) compute F F ; (2) given F, answer if F  represents a fingerprint in F F ; (3) given F, find all maximal locations of F in s . These problems are, respectively, solved in O(n+|L|log|?|) O ( n + | L | log | ? | ) , ?(|?|) ? ( | ? | ) , and ?(|?|+K) ? ( | ? | + K ) timewhere K is the number of maximal locations of F.
text fingerprinting naming maximal location character set text algorithm