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

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 \leq i \leq |T|$. In this paper we are interested in computing the set $\mathit{ans_i}$ of distinct substrings $w$ of $T_i$ such that $k_1 \leq |w| \leq k_2$, and $w$ contains some $p \in P$ as a prefix and some $s \in S$ as a suffix. Let $\sigma$ denote the alphabet size. Then, we show that after $O((\Vert P\Vert +\Vert S\Vert)\log\sigma)$-time preprocessing, the counting problem of outputting $|\mathit{ans_i}|$ on each iteration $i$ can be solved in $O(|T_i| \log\sigma)$ cumulative time, while the reporting problem can be solved in $O(|T_i| \log\sigma + |\mathit{ans_i}|)$ cumulative time, with both problems requiring only $O(|T_i|+\Vert P\Vert + \Vert S\Vert)$ working space. The preprocessing time can be reduced to $O(\Vert P\Vert +\Vert S\Vert)$ for integer alphabets of size polynomial with regard to $\Vert P\Vert +\Vert S\Vert$. Here, for a sequence of strings $A$, $\Vert A\Vert=\sum_{u\in A}|u|$. Our algorithms have possible applications to network traffic classification.