Theoretical Research of KMP Algorithm

KMP algorithm is one of classic string matching algorithms.A set K_j,for 1 <j≤m,which characterize a pattern prefix,and its partition are introduced,their some properties are discussed.Then,functions f and next are defined,the structure of K_j is described by f,a iterative computing method of f is proposed,the relationship between functions next and f is proved.Thus,mathematical principles of KMP algorithm is strictly established. Finally,the algorithm is described based on the iterative computing method of f and the relationship between functions next and f,and its complexity is analyzed.