Fast string matching with k differences

DOI10.1016/0022-0000(88)90045-1zbMath0655.68075OpenAlexW2074707165WikidataQ56813211 ScholiaQ56813211MaRDI QIDQ1109574

Gad M. Landau, Uzi Vishkin

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90045-1

zbMATH Keywords

string matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (29)

Algorithms For Computing Approximate Repetitions In Musical Sequences ⋮ Approximate pattern matching and transitive closure logics. ⋮ Sublinear approximate string matching and biological applications ⋮ Pattern matching in a digitized image ⋮ Boyer-Moore approach to approximate string matching ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ Matching patterns in strings subject to multi-linear transformations ⋮ A dynamic edit distance table ⋮ On updating suffix tree labels ⋮ Internal shortest absent word queries in constant time and linear space ⋮ Pattern matching under DTW distance ⋮ Elastic-degenerate string matching with 1 error ⋮ 2-dimensional palindromes with \(k\) mismatches ⋮ String matching with weighted errors ⋮ Double string tandem repeats ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Approximate string-matching with \(q\)-grams and maximal matches ⋮ An artificial neural network based approach for online string matching/filtering of large databases ⋮ Approximate string matching with suffix automata ⋮ Pattern matching in pseudo real-time ⋮ LCS approximation via embedding into locally non-repetitive strings ⋮ Simple and efficient string matching with k mismatches ⋮ Fast parallel and serial multidimensional approximate array matching ⋮ LCS Approximation via Embedding into Local Non-repetitive Strings ⋮ Improved approximate pattern matching on hypertext ⋮ Orthogonal Range Searching for Text Indexing ⋮ On minimizing pattern splitting in multi-track string matching ⋮ Fast and practical approximate string matching

Cites Work

• Efficient string matching with k mismatches
• Time-space-optimal string matching
• A fast string searching algorithm
• Fast Algorithms for Finding Nearest Common Ancestors
• RECOGNITION OF AN APPROXIMATE OCCURRENCE OF WORDS ON A TURING MACHINE IN REAL TIME
• Finding approximate patterns in strings
• Optimal parallel algorithms for string matching
• Optimal parallel pattern matching in strings
• Efficient randomized pattern-matching algorithms
• Fast Pattern Matching in Strings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast string matching with k differences