Average-optimal string matching

DOI10.1016/j.jda.2008.09.001zbMath1192.68195OpenAlexW2098102002MaRDI QIDQ1044048

Kimmo Fredriksson, Szymon Grabowski

Publication date: 10 December 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.09.001

zbMATH Keywords

optimalitystring matchingmultiple string matchingbit-parallelism

Mathematics Subject Classification ID

Searching and sorting (68P10) Formal languages and automata (68Q45)

Related Items (7)

Run-Length Encoded Nondeterministic KMP and Suffix Automata ⋮ BLIM: A new bit-parallel pattern matching algorithm overcoming computer word size limitation ⋮ Fast circular dictionary-matching algorithm ⋮ Multi-pattern matching algorithm with wildcards based on bit-parallelism ⋮ A faster quick search algorithm ⋮ Searching and Indexing Circular Patterns ⋮ Quasi-Linear-Time Algorithm for Longest Common Circular Factor

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bit-parallel witnesses and their applications to approximate string matching
• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• Bit-parallel (\(\delta ,\gamma\))-matching and suffix automata
• Bit-parallel approximate string matching algorithms with transposition
• Sequential and indexed two-dimensional combinatorial template matching allowing rotations
• NR‐grep: a fast and flexible pattern‐matching tool
• A fast string searching algorithm
• FLEXIBLE MUSIC RETRIEVAL IN SUBLINEAR TIME
• Efficient randomized pattern-matching algorithms
• The Complexity of Pattern Matching for a Random String
• Efficient string matching
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• Algorithms on Strings
• A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns
• Indexing Circular Patterns
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Average-optimal single and multiple approximate string matching
• String Processing and Information Retrieval

This page was built for publication: Average-optimal string matching