INVERSE PATTERN-MATCHING

Let a textstring T of n symbols from some alphabet Sigma and an intege r m < n be given. A pattern P of length m over Sigma is sought such th at P minimizes (alternatively, maximizes) the total number of pairwise character mismatches generated when P is compared with all m-characte r substrings of T. Two additional Variants of the problem are obtained by adding the constraint that P be (respectively, not be) a substring of T. Efficient sequential algorithms are proposed in this paper for the problem and its variants. (C) 1997 Academic Press.