Matching a set of strings with variable length don't cares

DOI10.1016/S0304-3975(97)88195-9zbMath0901.68037MaRDI QIDQ1391531

Gregory Kucherov, Michaël Rusinowitch

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

string matching algorithm

Mathematics Subject Classification ID

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

Related Items

A matching algorithm in PMWL based on CluTree ⋮ A linear time lower bound on McCreight and general updating algorithms for suffix trees ⋮ Multiple serial episodes matching ⋮ Mind the gap! ⋮ Online parameterized dictionary matching with one gap ⋮ Multi-pattern matching algorithm with wildcards based on bit-parallelism ⋮ Dictionary matching with a bounded gap in pattern or in text ⋮ Online recognition of dictionary with one gap ⋮ Parameterized dictionary matching and recognition with one gap ⋮ A faster algorithm for matching a set of patterns with variable length don't cares ⋮ Window-accumulated subsequence matching problem is linear ⋮ Efficient dynamic dictionary matching with DAWGs and AC-automata ⋮ Multi-subsequence searching ⋮ Dictionary matching with a few gaps ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for string matching with a sequence of don't cares
• The smallest automaton recognizing the subwords of a text
• Dynamic dictionary matching with failure functions
• Dynamic dictionary matching
• Parallel string matching with variable length don't cares
• Transducers and repetitions
• A data structure for dynamic trees
• On-line construction of suffix trees
• A Four Russians algorithm for regular expression pattern matching
• Complete inverted files for efficient text retrieval and analysis