How the character comparison order shapes the shift function of on-line pattern matching algorithms

AbstractString matching is the problem of finding all occurrences of a string …[0… m - 1] of length m called a pattern, in a longer string …[0…n - 1] of length n called a text. Several string matching algorithms have been designed to solve the problem in linear time; most of them work in two steps, called pattern preprocessing and text search step.The paper addresses the definition and computation of the shift function in the pattern preprocessing step of on-line string matching algorithms. The shift function depends essentially on the order the pattern characters are compared with the corresponding text characters.We consider a family … of algorithms that do not change the character comparison order J during execution and we present a uniform definition of shift function δJ for such algorithms via a function iminJ. The definition allows one to compute δJ in O(m log log m) time in the worst case, given iminJ, but sufficient conditions to compute δJ in O(m) time are provided. Computing iminJ requires O(m2) comparisons in general. We introduce the class of compact orders (which is the generalization of Knuth-Morris-Pratt, Boyer-Moore and Crochemore-Perrin character comparison orders) and we give algorithms to compute both function iminJ and shift function δJ in O(m) time for all compact orders.We show that given the order J and the pattern … there exists a set C of equivalent orders such that the function iminK can be computed in linear time given iminJ for all orders K ϵ C. Moreover, we characterize two orders in the set C that respectively minimize and maximize the values of the shift function and we show that for both those orders the shift function can be computed in linear time given iminJ