# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
\begin{table}
\begin{tabular}{c r r} \hline \hline \multirow{2}{*}{**Description**} & \multicolumn{2}{c}{**Running Time [ms]**} \\ \cline{2-3}  & **Same Strings** & **Different Strings** \\ \hline Random binary strings & 10.9 \(\pm\) 0.3 & 12.2 \(\pm\) 0.3 \\ English text 1 & 6.3 \(\pm\) 0.2 & 7.4 \(\pm\) 0.3 \\ English text 2 & 84.4 \(\pm\) 3.0 & 79.9 \(\pm\) 7.5 \\ DNA sequences & 89.8 \(\pm\) 3.1 & 82.9 \(\pm\) 7.0 \\ C++ source code & 87.2 \(\pm\) 3.0 & 80.7 \(\pm\) 7.3 \\ Single-letter strings (\(d=1\)) & 121.9 \(\pm\) 2.0 & 118.7 \(\pm\) 3.4 \\ Periodic strings (\(d=10\)) & 120.3 \(\pm\) 3.7 & 118.0 \(\pm\) 3.5 \\ Periodic strings (\(d=100\)) & 131.3 \(\pm\) 4.4 & 126.6 \(\pm\) 3.5 \\ Periodic strings (\(d=1000\)) & 137.5 \(\pm\) 4.7 & 134.2 \(\pm\) 4.3 \\ Periodic strings (\(d=4000\)) & 148.4 \(\pm\) 3.9 & 144.6 \(\pm\) 4.3 \\ Periodic strings (\(d=10\),000) & 142.2 \(\pm\) 5.3 & 140.5 \(\pm\) 5.2 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Running times on various types of strings, with \(|p|=200\),000, \(|s|=300\),000, and \(|t|=100\),000.

repeating an experiment on the same test case as well as across different test cases (different triples of strings \(s\), \(t\), \(p\)) of the same type. We will restrict the subsequent analysis to periodic strings with the length of period \(d=10\) and further limit the lengths of the input to \(|t|<|p|\leq|s|+|t|\). The pattern \(p\) should be longer than the inserted string \(t\) so that its occurrences can also span the entire inserted string (otherwise Algorithm 8 never gets executed). The pattern \(p\) also should not exceed the total length of the string after insertion, i.e., \(|s|+|t|\). Figure 6 shows a comparison of the running times of the different solutions presented in this paper: the quadratic-time solution based on dynamic programming (Section 2.3); its \(O(n\sqrt{n})\) improvement based on distinguished nodes (Section 2.4); the \(O(n\log n)\) \"geometric\" solution based on a plane sweep (Section 2.5); and lastly two variants of the solution based on Algorithm 8: the almost-linear solution where a disjoint-set forest is used in the implementation of Algorithm 11, and the truly linear solution where the static tree set union data structure is used instead. As expected, the quadratic and the \(O(n\sqrt{n})\) solutions are the slowest, and their running time grows in accordance with their asymptotic time complexity. For the other three solutions, however, it turns out that their running time _in practice_ is just the opposite of what one might expect given their _asymptotical_ complexity: the \(O(n\log n)\) solution is a clear winner in practice, being about three times faster than the almost-linear solution, which in turn is approx. 25 % faster than the truly linear solution; moreover, the \(O(n\log n)\) solution is much easier to implement. This illustrates the importance, in practice, of the constant factors hidden inside the \(O(\cdot)\) notation. Extrapolating the curves from Figure 6 suggests that it would take strings of a quite intractable length, approximately \(10^{24}\) characters, before the logarithmic factor in the running time of the plane-sweep solution would outweigh the advantage it currently enjoys due to its lower constant factor. The plane-sweep solution also has the advantage of requiring substantially less memory than the linear solution; in our implementation, the plane-sweep solution required \(\approx\)170 bytes of memory per character of \(p\), as compared to \(\approx\)390 bytes of the linear solution; and \(\approx\)45 bytes of memory per character of \(s\), as compared to \(\approx\)176 of the linear solution (though admittedly this latter figure could be reduced to about 80 at the cost of a mild additional inconvenience in the implementation).