A Four Russians algorithm for regular expression pattern matching

DOI10.1145/128749.128755zbMath0799.68104OpenAlexW2136238707MaRDI QIDQ4302816

Gene Myers

Publication date: 13 November 1994

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

finite automatonpattern matchingregular expressionfour Russian paradigmnode listing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10) Parallel algorithms in computer science (68W10)

Related Items (29)

Dynamic Set Intersection ⋮ Fast and compact regular expression matching ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ Minimized Thompson NFA ⋮ Mind the gap! ⋮ Matching a set of strings with variable length don't cares ⋮ Unnamed Item ⋮ Unnamed Item ⋮ String matching with variable length gaps ⋮ A faster algorithm for finding shortest substring matches of a regular expression ⋮ Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism ⋮ Online recognition of dictionary with one gap ⋮ Space-Efficient Representations for Glushkov Automata ⋮ Faster Algorithms for Weighted Recursive State Machines ⋮ Faster Bit-Parallel Algorithms for Unordered Pseudo-tree Matching and Tree Homeomorphism ⋮ A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem ⋮ Fast searching in packed strings ⋮ Exact matching of RNA secondary structure patterns ⋮ Unnamed Item ⋮ On the size of partial derivatives and the word membership problem ⋮ Compressing Regular Expressions’ DFA Table by Matrix Decomposition ⋮ Compact representations of automata for regular expression matching ⋮ Fast Searching in Packed Strings ⋮ From Regular Expression Matching to Parsing ⋮ Regular expression searching on compressed text ⋮ Unnamed Item ⋮ From regular expression matching to parsing ⋮ Dictionary matching with a few gaps ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges

This page was built for publication: A Four Russians algorithm for regular expression pattern matching