Optimal pattern matching algorithms

DOI10.1016/j.jco.2018.10.003zbMath1489.68417arXiv1604.08437OpenAlexW2963080472MaRDI QIDQ1734696

Gilles Didier

Publication date: 27 March 2019

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.08437

zbMATH Keywords

Markov chainspattern matchingaverage complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Designing optimal- and fast-on-average pattern matching algorithms
• An analytical comparison of two string searching algorithms
• String overlaps, pattern matching, and nontransitive games
• Average running time of the Boyer-Moore-Horspool algorithm
• An algorithm to compute the character access count distribution for pattern matching algorithms
• The Boyer-Moore-Horspool heuristic with Markovian input
• The exact online string matching problem
• Analysis of Boyer-Moore-Horspool string-matching heuristic
• Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics
• Exact Analysis of Horspool’s and Sunday’s Pattern Matching Algorithms with Probabilistic Arithmetic Automata
• The Complexity of Pattern Matching for a Random String
• Fast Pattern Matching in Strings
• Average case analysis of the Boyer‐Moore algorithm

This page was built for publication: Optimal pattern matching algorithms