1. Fast Algorithms for Computing the Statistics of Pattern Matching
- Author
-
Kai Jin and Danna Zhang
- Subjects
failure function ,General Computer Science ,Markov chain ,MathematicsofComputing_GENERAL ,Markov process ,Computer Science::Digital Libraries ,symbols.namesake ,Statistics ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,General Materials Science ,Computer Science::Symbolic Computation ,Pattern matching ,Mathematics ,Linear system ,High Energy Physics::Phenomenology ,General Engineering ,Sigma ,Variance (accounting) ,TK1-9971 ,Moment (mathematics) ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,KMP algorithm ,automaton ,statistics ,symbols ,ComputingMethodologies_DOCUMENTANDTEXTPROCESSING ,Embedding ,Computer Science::Programming Languages ,Electrical engineering. Electronics. Nuclear engineering ,Algorithm - Abstract
Pattern matching is a fundamental problem in theoretical computer science. The algorithms for pattern matching and the study on the statistics of pattern matching have found enormous applications in practical fields. In this paper, we revisit the Markov embedding approach for studying pattern matching in repeated experiments. For any pattern of length $m$ over alphabet $\Sigma $ , we show that the mean and variance of the waiting time of the pattern in iid experiments can be computed in $O(m)$ time based on Markov embedding technique, improving over the $O(|\Sigma | \cdot m)$ and $O(m^{2})$ naïve bounds. Our method extends to computing the $k$ -th moment of the waiting time, and it extends to computing other related statistics about pattern matching in repeated experiments, and it also extends to the case of Markov dependent experiments.
- Published
- 2021