Property Matching and Weighted Matching

In many pattern matching applications the text has some properties attached to various of its parts. Pattern Matching with Properties (Property Matching, for short), involves a string matching between the pattern and the text, and the requirement that the text part satisfies some property. Some immediate ex-amples come from molecular biology where it has long been a practice to consider special areas in the genome by their structure. It is straightforward to do sequential matching in a text with properties. However, indexing in a text with properties becomes difficult if we desire the time to be output dependent. We present an algorithm for indexing a text with properties in O(n log jj + n log logn) time for preprocessing and O(jP j log jj + to) per query, where n is the length of the text, P is the sought pattern, is the alphabet, and to is the number of occurrences of the pattern that satisfy some property . As a practical use of Property Matching we show how to solve Weighted Matching problems using techniques from Property Matching. Weighted sequences have been recently introduced as a tool to handle a set of sequences that are not identical but have many local similarities. The weighted sequence is