Efficient parameterized string matching

DOI10.1016/J.IPL.2006.06.009MaRDI QIDQ845838zbMATH OpenOpenAlexFDO

Authors Kimmo Fredriksson, Maxim Mozgovoy

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.06.009

zbMATH Keywords

algorithmsbit-parallelismsuffix automatonparameterized string matching

Mathematics Subject Classification ID

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

Recommendations

• Fast parameterized matching with \(q\)-grams
• Sublinear Algorithms for Parameterized Matching
• Algorithms – ESA 2004
• Parameterized pattern matching: Algorithms and applications
• Parameterized matching with mismatches

Cites work

• scientific article; zbMATH DE number 140461 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• scientific article; zbMATH DE number 910912 (Why is no real title available?)
• A fast string searching algorithm
• Algorithms on Strings, Trees and Sequences
• Alphabet dependence in parameterized matching
• Efficient string matching
• Faster suffix tree construction with missing suffix links
• Multiple matching of parameterized patterns
• Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance
• Speeding up two string-matching algorithms
• Suffix Arrays: A New Method for On-Line String Searches
• The Complexity of Pattern Matching for a Random String
• The smallest automaton recognizing the subwords of a text

Cited in

(22)

• scientific article; zbMATH DE number 140453 (Why is no real title available?)
• The structural border array
• Generalized String Matching
• Fast and flexible packed string matching
• Parameterized searching with mismatches for run-length encoded strings
• Simpler FM-index for parameterized string matching
• Secure parameterized pattern matching
• The finite automata approaches in stringology
• Alphabet dependence in parameterized matching
• Parameterized matching on non-linear structures
• Computing the parameterized Burrows-Wheeler transform online
• Weighted approximate parameterized string matching
• Position heaps for parameterized strings
• Space-efficient dictionaries for parameterized and order-preserving pattern matching
• Fast parameterized matching with \(q\)-grams
• Efficient string-matching allowing for non-overlapping inversions
• Counting Parameterized Border Arrays for a Binary Alphabet
• A brief history of parameterized matching problems
• Verifying and enumerating parameterized border arrays
• A prefix array for parameterized strings
• Algorithms – ESA 2004
• Efficient parameterized pattern matching in sublinear space

This page was built for publication: Efficient parameterized string matching

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