The content-based publish-subscribe (pub-sub) paradigm for system design is becoming increasingly popular, offering unique benefits for many data-intensive applications. Coupled with peer-to-peer technology, it can serve as a central building block for developing data-dissemination applications deployed over a large-scale network infrastructure. A key open problem in creating large-scale content-based pub-sub infrastructures relates to efficiently and accurately matching subscriptions with substring predicates to incoming events. This work addresses this issue.