Abstract:
KMP algorithm is one of classic string matching algorithms.A set
Kj,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
Kj 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.