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

DOI10.3390/A4040285MaRDI QIDQ1736492zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tobias Marschall, Sven Rahmann

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

minimizationanalysis of algorithmspattern matchingfinite automatondeterministic arithmetic automatonprobabilistic arithmetic automaton

Mathematics Subject Classification ID

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

Recommendations

• Exact analysis of Horspool's and Sunday's pattern matching algorithms with probabilistic arithmetic automata
• Analysis of Boyer-Moore-Horspool string-matching heuristic
• Designing optimal- and fast-on-average pattern matching algorithms
• On the Expected Sublinearity of the Boyer–Moore Algorithm
• Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics

Cites work

• scientific article; zbMATH DE number 432780 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1998338 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• scientific article; zbMATH DE number 1794216 (Why is no real title available?)
• A fast string searching algorithm
• Analysis of Boyer-Moore-Horspool string-matching heuristic
• Average case analysis of the Boyer‐Moore algorithm
• Average running time of the Boyer-Moore-Horspool algorithm
• Exact analysis of Horspool's and Sunday's pattern matching algorithms with probabilistic arithmetic automata
• Fast Pattern Matching in Strings
• Motif statistics.
• Multiple pattern matching: a Markov chain approach
• Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
• Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics
• Re-describing an algorithm by Hopcroft
• Speeding up two string-matching algorithms
• The Boyer-Moore-Horspool heuristic with Markovian input

Cited in

(5)

• Optimal pattern matching algorithms
• Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics
• Designing optimal- and fast-on-average pattern matching algorithms
• Waiting time and complexity for matching patterns with automata
• Exact analysis of Horspool's and Sunday's pattern matching algorithms with probabilistic arithmetic automata

Describes a project that uses

Uses Software

• Regexpcount

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

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