Incremental String Comparison

DOI10.1137/S0097539794264810zbMath0907.68075WikidataQ56813213 ScholiaQ56813213MaRDI QIDQ4388886

Eugene W. Myers, Jeanette P. Schmidt, Gad M. Landau

Publication date: 10 May 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794264810

zbMATH Keywords

dynamic programming; string matching; edit-distance

Mathematics Subject Classification ID

68P99: Theory of data

Related Items

Unnamed Item, Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product, Unnamed Item, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, Unnamed Item, Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation, Small-space LCE data structure with constant-time queries, EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS, Approximate periods of strings, Practical Performance of Space Efficient Data Structures for Longest Common Extensions., Linear-space S-table algorithms for the longest common subsequence problem, Pattern matching under DTW distance, Longest common extensions in trees, Monge properties of sequence alignment, Dynamic edit distance table under a general weighted cost function, Pattern matching in pseudo real-time, Longest common subsequence problem for unoriented and cyclic strings, A dynamic edit distance table, Semi-local longest common subsequences in subquadratic time, Overlap matching., Approximate string matching with compressed indexes, On almost Monge all scores matrices, Approximate swapped matching., \(k\)-approximate quasiperiodicity under Hamming and edit distance, Approximating the geometric edit distance, Alignments of mitochondrial genome arrangements: applications to metazoan phylogeny, Speeding up the detection of tandem repeats over the edit distance, Efficient all path score computations on grid graphs, Time-space trade-offs for longest common extensions, Two algorithms for LCS consecutive suffix alignment, Time-Space Trade-Offs for Longest Common Extensions, Longest Common Extensions in Trees, Longest Common Extensions in Sublinear Space, Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance, APPROXIMATION ALGORITHMS FOR LOCAL ALIGNMENT WITH LENGTH CONSTRAINTS, FINDING ALL APPROXIMATE GAPPED PALINDROMES, Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions