Tobias Reichl

Sequential Pattern Matching -- Analysis of Knuth-Morris-Pratt Type Algorithms Using the Subadditive Ergodic Theorem

Abstract

Based on an article by Mireille Regnier and Wojciech Szpankowski this report outlines the complexity analysis of Knuth-Morris-Pratt type algorithms using the Subadditive Ergodic Theorem, Martingales and Azuma's Inequality.
Using the Subadditive Ergodic Theorem we will prove the existence of a linearity constant for worst and average case. Although the Subadditive Ergodic Theorem doesn't indicate a way to compute the linearity constant, we may use Azuma's Inequality to show that the number of comparisons done is well concentrated around its mean value.