CSC 3102 Chapter : Csc3102KMPStringMatcher
Document Summary
The knuth-morris-pratt algorithm: the string matching problem, the naive string matching algorithm, the kmp string matching algorithm. Consider text in an array t [1 . n] and a pattern in array. P occurs with shift s in t , then we call s a valid shift; otherwise, we call s an invalid shift. The string matching problem is the problem of nding all valid shifts. {t a string of n characters representing the host text, P a string of m characters representing the pattern text, S array with valid and invalid shifts. } j
