We concentrate in this paper on multiple pattern matching, in which a set of patterns S = {P_1, ... , P_k}, rather than a single one, is to be located in a given text T. This problem has been treated in several works, including Aho and Corasick, Commentz-Walter, Uratani and Takeda and Crochemore et al. None of these algorithms assumes any relationships between the individual patterns. Nevertheless, there are many situations where the given strings are not necessarily independent.
展开▼