Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions

Abstract: Let two static sequences of strings

P

and

S

, representing prefix and suffix conditions respectively, be given as input for preprocessing. For the query, let two positive integers

k_{1}

and

k_{2}

be given, as well as a string

T

given in an online manner, such that

T_{i}

represents the length-

i

prefix of

T

for

1 l e q i l e q | T |

. In this paper we are interested in computing the set

m a t h i t a n s_{i}

of distinct substrings

w

of

T_{i}

such that

k_{1} l e q | w | l e q k_{2}

, and

w

contains some

p i n P

as a prefix and some

s i n S

as a suffix. More specifically, the counting problem is to output

| m a t h i t a n s_{i} |

, whereas the reporting problem is to output all elements of

m a t h i t a n s_{i}

, for each iteration

i

. Let

s i g m a

denote the alphabet size, and for a sequence of strings

A

,

V e r t A V e r t = s u m_{u i n A} | u |

. Then, we show that after

O ((V e r t P V e r t + V e r t S V e r t) l o g s i g m a)

-time preprocessing, the solutions for the counting and reporting problems for each iteration up to

i

can be output in

O (| T_{i} | l o g s i g m a)

and

O (| T_{i} | l o g s i g m a + | m a t h i t a n s_{i} |)

total time. The preprocessing time can be reduced to

O (V e r t P V e r t + V e r t S V e r t)

for integer alphabets of size polynomial with regard to

V e r t P V e r t + V e r t S V e r t

. Our algorithms have possible applications to network traffic classification.

Cites Work

This page was built for publication: Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions