Fast and compact regular expression matching
From MaRDI portal
Publication:2378530
DOI10.1016/j.tcs.2008.08.042zbMath1155.68022OpenAlexW2137939491MaRDI QIDQ2378530
Philip Bille, Martín Farach-Colton
Publication date: 8 January 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.042
regular expression matchingapproximate regular expression matching: string edit distancefour Russian techniquesubsequence indexing
Related Items (18)
Subsequence automata with default transitions ⋮ New tabulation and sparse dynamic programming based techniques for sequence similarity problems ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ Unnamed Item ⋮ Space-efficient STR-IC-LCS computation ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ Space-Efficient Representations for Glushkov Automata ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem ⋮ Faster approximate string matching for short patterns ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ Unnamed Item ⋮ Compact representations of automata for regular expression matching ⋮ From Regular Expression Matching to Parsing ⋮ Unnamed Item ⋮ From regular expression matching to parsing ⋮ Fast distance multiplication of unit-Monge matrices ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Bounded ordered dictionaries in O(log log N) time and O(n) space
- Approximate matching of regular expressions
- A faster algorithm computing string edit distances
- Preserving order in a forest in less than logarithmic time and linear space
- Faster approximate string matching
- New techniques for regular expression searching
- Directed acyclic subsequence graph -- overview
- Searching subsequences
- Deterministic Dictionaries
- NR‐grep: a fast and flexible pattern‐matching tool
- A fast bit-vector algorithm for approximate string matching based on dynamic programming
- Space efficient dynamic stabbing with fast queries
- Rank/select operations on large alphabets
- New Algorithms for Regular Expression Matching
- Design and implementation of an efficient priority queue
- Algorithms on Strings, Trees and Sequences
- A Four Russians algorithm for regular expression pattern matching
- Fast text searching for regular expressions or automaton searching on tries
- The String-to-String Correction Problem
- A Subquadratic Algorithm for Approximate Regular Expression Matching
- Regular expression pattern matching for XML
- Programming Techniques: Regular expression search algorithm
This page was built for publication: Fast and compact regular expression matching