Computer Science Colloquium, 2003-2004

Revital Eres
Department of Computer Science, University of Haifa
May 19th, 2004

Scaled and Permuted String Matching

The well-known problem in stringology is the exact string matching problem which is finding all the occurrences of a pattern in a text. Based on "real-life" problems from varied fields like biology, natural languages and image processing it became clear that an approximate version of this problem is much more practical. As a result the problem of finding all the substrings of a text that match some transformation of the pattern has been extensively studied. Most of the theoretical work has dealt with one type of transformation in a time. This research is the first attempt to deal with two types of transformations together - Scaling and Permutations.

Given a text of length n and a pattern of length m we developed an algorithm which finds all occurrences of the pattern in the text in all possible scales and permutations in O(n).

This work was made as part of my M.A thesis with the supervision of Prof. Gad. M. Landau and together with Dr. Ayelet Butman.


Shuly Wintner
Last modified: Thu Apr 29 14:32:16 IDT 2004