Generalized String Matching
From MaRDI portal
Publication:3790661
DOI10.1137/0216067zbMath0646.68079OpenAlexW1989204408MaRDI QIDQ3790661
No author found.
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216067
Related Items (84)
New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings ⋮ On lower bounds for read-\(k\)-times branching programs ⋮ Pattern matching in a digitized image ⋮ Two-dimensional pattern matching with rotations ⋮ Swap and mismatch edit distance ⋮ Efficient special cases of pattern matching with swaps ⋮ Resource scheduling with variable requirements over time ⋮ An acceleration of FFT-based algorithms for the match-count problem ⋮ Computing covers using prefix tables ⋮ \(L_{1}\) pattern matching lower bound ⋮ Pattern matching with don't cares and few errors ⋮ Efficient matching of nonrectangular shapes. ⋮ Data structures and algorithms for approximate string matching ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ On pattern matching with \(k\) mismatches and few don't cares ⋮ The complexity of approximate pattern matching on de Bruijn graphs ⋮ The approximate swap and mismatch edit distance ⋮ A filtering algorithm for \(k\)-mismatch with don't cares ⋮ Covering problems for partial words and for indeterminate strings ⋮ Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ Computing primitively-rooted squares and runs in partial words ⋮ Longest common extension ⋮ Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance ⋮ Computing Primitively-Rooted Squares and Runs in Partial Words ⋮ Pattern matching in hypertext ⋮ Can we recover the cover? ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ Secure two-party input-size reduction: challenges, solutions and applications ⋮ On the relationship between histogram indexing and block-mass indexing ⋮ Indexing a sequence for mapping reads with a single mismatch ⋮ A Black Box for Online Approximate Pattern Matching ⋮ Indeterminate string inference algorithms ⋮ Mismatch sampling ⋮ Pattern matching in the Hamming distance with thresholds ⋮ Modulated string searching ⋮ Extending alignments with \(k\)-mismatches and \(\ell\)-gaps ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A lower-variance randomized algorithm for approximate string matching ⋮ Pattern matching with address errors: rearrangement distances ⋮ A new approach to regular \& indeterminate strings ⋮ Time-space tradeoffs for algebraic problems on general sequential machines ⋮ Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance ⋮ Filtering degenerate patterns with application to protein sequence analysis ⋮ On string matching with mismatches ⋮ Indeterminate strings, prefix arrays \& undirected graphs ⋮ IDPM: An Improved Degenerate Pattern Matching Algorithm for Biological Sequences ⋮ Generalized function matching ⋮ Fast average-case pattern matching by multiplexing sparse tables ⋮ Efficient and Secure Generalized Pattern Matching via Fast Fourier Transform ⋮ THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW ⋮ NECKLACE SWAP PROBLEM FOR RHYTHMIC SIMILARITY MEASURES ⋮ Fast pattern-matching on indeterminate strings ⋮ On approximate pattern matching with thresholds ⋮ A randomized numerical aligner (rNA) ⋮ Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics ⋮ Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching ⋮ ALGORITHMIC COMBINATORICS ON PARTIAL WORDS ⋮ Matching with don't-cares and a small number of mismatches ⋮ A black box for online approximate pattern matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hardness of comparing two run-length encoded strings ⋮ Unnamed Item ⋮ Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances ⋮ Faster pattern matching with character classes using prime number encoding ⋮ \(k\)-difference matching in amortized linear time for all the words in a text ⋮ Circular pattern matching with \(k\) mismatches ⋮ Approximate pattern matching on elastic-degenerate text ⋮ An algorithm for string matching with a sequence of don't cares ⋮ Hamming Distance Completeness ⋮ Approximating Approximate Pattern Matching ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Comparing Degenerate Strings ⋮ AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS ⋮ Fast and practical approximate string matching ⋮ Approximate swapped matching. ⋮ Squares and primitivity in partial words ⋮ Inferring an indeterminate string from a prefix graph ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Fast algorithms for approximately counting mismatches ⋮ Recent advances in text-to-pattern distance algorithms ⋮ Faster Online Elastic Degenerate String Matching
This page was built for publication: Generalized String Matching
