1987/12/01 by Karl Abrahamson · 6 citations
Computer Science · #Algorithms and Data Compression #semigroups and automata theory #Network Packet Processing and Optimization
paper · doi:10.1137/0216067
Given a pattern string of length n and an object string of length m, the string matching problem asks for the positions of all occurrences of the pattern in the object string. This paper investigates a generalization of string matching, in which the pattern is a sequence of pattern elements, each compatible with a set of symbols. The alphabet of symbols is infinite, with its members encoded in a finite alphabet. In contrast to standard string matching, which can be solved in simultaneous linear time and constant space, it is shown that generalized string matching requires a time-space product of Ω (n2 / log n) on a powerful model of computation, when the alphabet is restricted to n symbols. Our proof uses a method of Borodin. The obvious algorithm for generalized string matching requires time O(NM), where N is the length of the encoding of the pattern, and M is that of the object string. We describe an algorithm which solves generalized string matching in time O(N + M + mN^1 / 2 polylog (n)).