Verifying candidate matches in sparse and wildcard matching

DOI10.1145/509907.509992zbMath1192.68819OpenAlexW1996113955MaRDI QIDQ3579248

Ramesh Hariharan, Richard John Cole

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.509992

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Related Items

Set intersection and sequence matching with mismatch counting ⋮ Simple deterministic wildcard matching ⋮ Pattern matching with don't cares and few errors ⋮ Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees ⋮ Finding submasses in weighted strings with fast Fourier transform ⋮ Permuted function matching ⋮ A filtering algorithm for \(k\)-mismatch with don't cares ⋮ Pattern matching with wildcards using words of shorter length ⋮ Covering problems for partial words and for indeterminate strings ⋮ Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ On the average-case complexity of pattern matching with wildcards ⋮ Algorithms for path-constrained sequence alignment ⋮ Approximate String Matching with Address Bit Errors ⋮ A Black Box for Online Approximate Pattern Matching ⋮ Unnamed Item ⋮ Multi-pattern matching algorithm with wildcards based on bit-parallelism ⋮ String matching with up to \(k\) swaps and mismatches ⋮ An algorithmic toolbox for periodic partial words ⋮ Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams ⋮ Streaming pattern matching with \(d\) wildcards ⋮ Necklaces, convolutions, and \(X+Y\) ⋮ Motif patterns in 2D ⋮ Incremental discovery of the irredundant motif bases for all suffixes of a string in \(O(n^2\log n)\)time ⋮ String indexing for patterns with wildcards ⋮ Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics ⋮ Matching with don't-cares and a small number of mismatches ⋮ A black box for online approximate pattern matching ⋮ Periodicity in data streams with wildcards ⋮ Unnamed Item ⋮ Faster pattern matching with character classes using prime number encoding ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard ⋮ Approximate string matching with address bit errors ⋮ On minimizing pattern splitting in multi-track string matching ⋮ Polynomial modular product verification and its implications ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Fast Convolutions of Packed Strings and Pattern Matching with Wildcards