# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
On the whole, the linear solution consumed about 2.5 to 3 times as much memory as the plane-sweep solution; for example, solving a test case with \(|t|=2\cdot 10^{6}\), \(|p|=9\cdot 10^{6}\), and \(|s|=10^{7}\) required \(\approx\)1.83 GB of memory with the plane-sweep solution vs. \(\approx\)4.95 GB with the linear solution. Thus, dealing with the strings whose lengths are in the tens of millions is just barely feasible on a typical desktop computer, while lengths in the hundreds of millions would not be feasible. Figure 6: Comparison of the running times of different solutions, for \(|p|=3|t|\) and \(|s|=5|t|\). In Figure 7, we compare the performance of the almost-linear solution (using a disjoint-set forest in Algorithm 11) with the truly linear solution (which uses the static tree set union data structure instead). We show the results for different sizes of the inserted string \(t\), with the other two strings being proportionally longer: \(|p|=3|t|\), \(|s|=5|t|\). Both solutions exhibit linear behavior (as expected, considering that the non-linear term in the complexity of the almost-linear solution is the very slowly growing inverse Ackermann's function) but the almost-linear solution turns out to be faster in practice: with the almost-linear instead of the linear implementation of union-find, Algorithm 11 runs approximately 2.8 times faster and the solution as a whole (of which Algorithm 11 is only a small part) runs approx. 25 % faster. Note that we did not optimize the implementation for speed as we are interested in its asymptotic properties, therefore this comparison might not reflect the true potential of each method (for example, [PERSON] and [PERSON] ([19], p. 249) reported that in some of their experiments, the running time of their static tree set union data structure was only 0.6-0.7 times as long as that of the disjont-set forests). In the remainder of this section, we will report the results of the linear solution. We have also analyzed the contribution of each part of the algorithm to its total running time. Here we provide a breakdown for the case of periodic strings (\(d=10\)) of lengths \(|s|=300\),000, \(|t|=1\),000,000, and \(|p|=|t|+|s|/2\), thus at the middle of the \"interesting\" range of \(|p|\) (i.e., \(|t|<|p|\leq|s|+|t|\)). Algorithm 8 spends 480 ms in the following ways:

* It spent 263 ms (54.7 %) on preprocessing to support constant-time LCP queries (this includes building suffix trees of \(p\) and \(p^{\text{s}}\)). * It spendt 17 ms (3.6 %) on counting early and late occurrences of \(p\) (steps 2 and 5 of Algorithm 8; described in more detail as Algorithm 9 in Section 2.6.1). * It spent 133 ms (27.7 %) on processing the ancestor queries (steps 3 and 6 of Algorithm 8; described in more detail as Algorithm 11 in Section 2.6.3). This includes the initialization of the static tree set union data structure. * It spent 19 ms (3.9 %) on counting the remaining occurrences of \(p\) (step 7 of Algorithm 8; described in more detail as Algorithm 10 in Section 2.6.2). * It spent 48 ms (10.1 %) on everything else: computing the various prefix and suffix tables from the KMP algorithm, counting those occurrences of \(p\) in \(s[:k]\)\(t\)s\([k:]\) that do not span the entire \(t\) (i.e., the first four types of occurrences from Section 2.2), and cleanup at the end of the algorithm. Figure 7: Comparison of the almost-linear union-find data structure with the truly linear one, for \(|p|=3|t|\) and \(|s|=5|t|\). The left chart shows the running times of the solution as a whole, the right chart shows only the time spent on Algorithm 11 (including the initialization of the union-find data structure). The relative amount of time spent on different parts of the solution remains fairly stable as the length of the pattern \(p\) varies (while the strings \(s\) and \(t\) are kept constant); this is illustrated by the stacked area chart on Figure 8. Major changes only occur when certain parts of the solution can be skipped altogether.