Analysis Of Algorithms Based On Markov Chains Model

String Matching is a fundamental component of computer science, including text editing, data retrieval, symbol manipulation, searching engine and so on. Algorithm complexity is a ruler to measure running efficiency of program. So many computer scientists are interested in this topic. In this paper, We study the Markov chain model on the automaton tailored to text, and derive exact analysis for the average case performance of the brute-force and KMP algorithm.The organization of this paper is as follows:1. In the first chapter, we review the background and some related definitions of string matching and algorithm complexity.2. In the second chapter, the two classic algorithms are described.3. The third chapter mainly discusses some theory related to Markov chains.4. The last chapter then considers analysis of algorithms presented, in which two main theorems are derived.