Affiliations: Algorithm Design Group, King’s College London, Strand, London WC2R 2LS, U.K. Maxime.Crochemore@kcl.ac.uk | Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland. kubica@mimuw.edu.pl | Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland. walen@mimuw.edu.pl | Algorithm Design Group, King’s College London, Strand, London WC2R 2LS, U.K. csi@dcs.kcl.ac.uk | AlEDA Group, Department of CSE, BUET, Dhaka-1000, Bangladesh. msrahman@cse.buet.ac.bd
Note: [] Address for correspondence: AlEDA Group, Department of CSE, BUET, Dhaka-1000, Bangladesh
Abstract: In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both the cases, we develop efficient solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.
Keywords: algorithms, data structures, pattern matching, strings
