PDMI TUM State University St. Petersburg
Steklov Institute St. Petersburg Technische Universität München State University St. Petersburg

Joint Advanced Student School (JASS)

Course 1: Complexity Analysis of String Algorithms


St. Petersburg - Sunday, March 28 through Wednesday, April 7, 2004

Roland Aydin

Analysis of Pattern Occurances


Abstract

This paper will summarize the proof for the formula to compute the expected number of occurrences of a given pattern H in a text of size n. The intuitive solution of E[O_n(H)]=P(H)(n-m+1) will be verified utilising generating functions. Frequency analysis will rely on the decomposition of the text T onto languages, the so-called initial, minimal, and tail languages. Going from there to their generating functions both for a Markovian and a Bernoulli environment, the formula will be shown to work due to properties of the respective generating functions.


Presentation:
08 Aydin Roland Analysis of pattern occurrences.pdf
Paper:
Chapter 8 (Postscript PS, PDF PDF) of the proceedings (Postscript PS, PDF PDF).