Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance

DOI10.1007/978-3-319-19315-1_5zbMath1396.68037OpenAlexW1766660969MaRDI QIDQ2946041

Solon P. Pissis, W. F. Smyth, Costas S. Iliopoulos, Carl Barton

Publication date: 15 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19315-1_5

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items (4)

Linear-Time Computation of Prefix Table for Weighted Strings ⋮ Checking whether a word is Hamming-isometric in linear time ⋮ Linear-time computation of prefix table for weighted strings {\&} applications ⋮ Efficient Identification of k-Closed Strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The longest common extension problem revisited and applications to approximate string searching
• Construction of Aho Corasick automaton in linear time for integer alphabets
• Prefix Table Construction and Conversion
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• An O(n log n) algorithm for finding all repetitions in a string
• Approximate All-Pairs Suffix/Prefix Overlaps
• Finding All Approximate Gapped Palindromes
• Generalized String Matching
• Incremental String Comparison
• Inducing the LCP-Array
• Algorithms on Strings
• Average-optimal single and multiple approximate string matching

This page was built for publication: Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance