Faster query algorithms for the text fingerprinting problem

DOI10.1016/j.ic.2011.04.001zbMath1216.68352OpenAlexW2059372536MaRDI QIDQ549671

Biing-Feng Wang, Wing-Kai Hon, Chi-Yuan Chan, Hung-I Yu

Publication date: 18 July 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2011.04.001

zbMATH Keywords

fingerprintscombinatorial algorithms on wordstext indexingPatricia trie

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items

Indexing and querying color sets of images, Various improvements to text fingerprinting, Indexing and querying character sets in one- and two-dimensional words

Cites Work

• Unnamed Item
• Unnamed Item
• New algorithms for text fingerprinting
• Efficient text fingerprinting via Parikh mapping
• Improved approximate common interval
• Character sets of strings
• Deterministic Dictionaries
• The string B-tree
• Fast Algorithms for Finding Nearest Common Ancestors
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• New Algorithms for Text Fingerprinting
• Combinatorial Pattern Matching