On 2-Tuple String Matching

Consider the following two problems. Problem 1. We are given a collection of 2-tuples T={T_1,...,T_k} where each T_i=(T_i^1,T_i^2), for two strings T_i^1 and T_i^2. This collection may be preprocessed. A query takes as input a pattern tuple P=(P^1,P^2) and the problem is to determine all tuples T_i for which P^1 is a substring of T_i^1 and P^2 is a substring of $T_i^2. Problem 2. We are given a collection of documents D={D_1,...,D_k} that may be preprocessed. Each query is a pair of pattern strings p_1 and p_2, and the goal is to determine the set of all documents that contain both patterns as substrings. In this paper, we show that these two problems are related and make progress on solving them efficiently by proposing the first non trivial results.