Single and Multiple Consecutive Permutation Motif Search

Let

t

be a permutation (that shall play the role of the

text

) on [

n

] and a motif

p

be a sequence of

m

distinct integer(s) of [

n

],

m

 ≤ 

n

. The motif

p

occurs in

t

in position

i

if and only if

p

1

…

p

m

is order-isomorphic to

t

i

…

t

i

 + 

m

 − 1

, that is, for all 1 ≤ 

k

 < ℓ ≤ 

m

,

p

k

 > 

p

ℓ

if and only if

t

i

 + 

k

 − 1

 > 

t

i

 + ℓ − 1

. Searching for a motif

p

in a text

t

consists in identifying all occurrences of

p

in

t

. We first present a forward automaton which allows us to search for

p

in

t

in

O

(

m

2

loglog

m

 + 

n

) time. We then introduce a Morris-Pratt automaton representation of the forward automaton which allows us to reduce this complexity to

O

(

m

loglog

m

 + 

n

) at the price of an additional amortized constant term. The latter automaton occupies

O

(

m

) space. We then extend the problem to search for a set of motifs and exhibit a specific Aho-Corasick like algorithm. Next we present a sub-linear average case search algorithm running in

$O\left(\frac{m\log m}{\log\log m}+\frac{n\log m}{m\log\log m}\right)$

time, that we eventually prove to be optimal on average.