#
11th International Conference, SPIRE 2004, Padova, Italy, October 5-8, 2004. Proceedings

*Real Scaled Matching*refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an

*arbitrary real-sized*scale, appears. Real scaled matching is an important problem that was originally inspired by Computer Vision. In this paper, we present a new, more precise and realistic, definition for one dimensional real scaled matching,...

*U*={

*T*

_{1},

*T*

_{2}, ... ,

*T*

_{ℓ}}, the longest common repeat problem is to find the longest common substring that appears at least twice in each string of

*U*. We also consider reversed and reverse-complemented repeats as well as normal repeats. We present a linear time algorithm for the longest common repeat problem.

*set*of patterns

*S*={

*P*

_{1}, ...,

*P*

_{ k }}, rather than a single one, is to be located in a given text

*T*. This problem has been treated in several works, including Aho and Corasick, Commentz-Walter, Uratani and Takeda and Crochemore et al. None of these algorithms assumes any relationships between...

*string matching*problem is to find all the occurrences of a given pattern

*x*=

*x*

_{1}

*x*

_{2}···

*x*

_{ m }in a large text

*y*=

*y*

_{1}

*y*

_{2}···

*y*

_{ n }, where both

*x*and

*y*are sequences of symbols drawn from a finite character set Σ of size

*σ*.

*scaled permuted string matching*is to find all occurrences of a pattern in a text, in all possible scales and permutations. Given a text of length

*n*and a pattern of length

*m*we present an

*O*(

*n*) algorithm.

*O*((

*m*

^{2}+ loglog

*σ*)...

*O*(

*n*

^{2}) computational complexity and linear memory complexity with respect to the length

*n*of the...