Regular expression matching with multi-strings and intervals

MaRDI QIDQ5417708zbMATH OpenFDO

Authors Philip Bille, Mikkel Thorup

Publication date 22 May 2014

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• New Algorithms for Regular Expression Matching
• Faster Regular Expression Matching
• Approximate regular expression matching with multi-strings
• scientific article; zbMATH DE number 1962812
• Online matching of multiple regular patterns with gaps and character classes

Cited in

(18)

• A faster algorithm for finding shortest substring matches of a regular expression
• Descriptional complexity of regular languages
• From regular expression matching to parsing
• A comparative study of dictionary matching with gaps: limitations, techniques and challenges
• Online parameterized dictionary matching with one gap
• Online recognition of dictionary with one gap
• Dictionary matching with a few gaps
• Approximate regular expression matching with multi-strings
• Mind the gap!
• Motif matching using gapped patterns
• String matching with variable length gaps
• From Regular Expression Matching to Parsing
• Space-efficient representations for Glushkov automata
• Fast identification of heavy hitters by cached and packed group testing
• Gapped string indexing in subquadratic space and sublinear query time
• Longest common substring with gaps and related problems
• Compressed dictionary matching on run-length encoded strings
• Compact representations of automata for regular expression matching

Describes a project that uses

Uses Software

• PERL

This page was built for publication: Regular expression matching with multi-strings and intervals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5417708)