

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png) 

![0_image_2.png](0_image_2.png) 

gorithms as functions of the sequence length. The experiments are performed using a computer with 3GB RAM and IntelCore 2 Duo CPU 2.33GHz. In our experiments, we used a KDE corpus [31] for sequences up to 5 million, while the sequences longer than 5 million are created by the concatenation of the KDE corpus on itself. We consider four different implementation cases depending on the sequence length:
Case I: This corresponds to short sequences, with the length shorter than 4 million. This case corresponds to the basic version of the FB algorithm (Algorithm 1). In this case, the sequence is stored in RAM and the RAM usage of both algorithms linearly grows with the sequence length (Figure 3a). However, the FB algorithm uses O(N
2T + M) memory for storing intermediate results and its RAM usage grows faster in comparison to the EMP, which needs fixed-size additional space O(N
2 + NM). RAM usage growth reflects on the computational performances of FB algorithm, which runs faster then the EMP for the sequences with the length up to 4.5 million.

As Figure 3a shows, at the sequence length of 3 millions FB RAM usage becomes considerable and the FB growth becomes