An algorithm to compute the character access count distribution for pattern matching algorithms

DOI10.3390/a4040285zbMath1461.68270DBLPjournals/algorithms/MarschallR11OpenAlexW2105205612WikidataQ61704584 ScholiaQ61704584MaRDI QIDQ1736492

Sven Rahmann, Tobias Marschall

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a4040285

zbMATH Keywords

analysis of algorithmsminimizationfinite automatonpattern matchingdeterministic arithmetic automatonprobabilistic arithmetic automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithms on strings (68W32)

Related Items (2)

Optimal pattern matching algorithms ⋮ Designing optimal- and fast-on-average pattern matching algorithms

Uses Software

• Regexpcount

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multiple pattern matching: a Markov chain approach
• Average running time of the Boyer-Moore-Horspool algorithm
• Speeding up two string-matching algorithms
• Re-describing an algorithm by Hopcroft
• Motif statistics.
• The Boyer-Moore-Horspool heuristic with Markovian input
• A fast string searching algorithm
• 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
• Fast Pattern Matching in Strings
• Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
• Average case analysis of the Boyer‐Moore algorithm

This page was built for publication: An algorithm to compute the character access count distribution for pattern matching algorithms