# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
In \(T_{\mathsf{P}}\) each node has a smaller value than its children, therefore \(w\) is the smallest member of \(A_{w}\). If some query has \(u_{k}\in A_{w}\) and \(b_{k}=v\), this means that \(u_{k}\) is a descendant of \(w\) and that all the nodes on the path from \(u_{k}\) to \(w\), except \(w\) itself, are greater than \(v\); therefore the path for this query will rise from \(u_{k}\) to \(w\) and then stop; thus step 4 of our algorithm is correct in reporting \(w\) as the answer to this query. Step 5 ensures that the loopinvariant is maintained into the next iteration. Step 3 requires us to sort the queries by \(b_{k}\), which can be achieved in linear time using counting sort. The time complexity of this algorithm depends on how we implement the union-find data structure \(F\). The traditional implementation using a disjoint-set forest results in a time complexity of \(O((p+s)\alpha(p+s,p))\) for Algorithm 11[18], and hence \(O(t+(p+s)\alpha(p+s,p))\) for the solution of our problem as a whole. Here \(\alpha\) is the inverse Ackermann function, which grows very slowly, making this solution almost linear. However, to obtain a truly linear solution, we can use the slightly more complex _static tree set union_ data structure due to [PERSON] and Tarjan [19, 20], which assumes that the elements are arranged in a tree and that the union operation is always performed between a set containing some node of the tree and the set containing its parent; hence this structure is perfectly suited to our needs. (A minor note to anyone intending to reimplement their approach: ([20], p. 212) uses the _macrofind_ operation in step 7 of _find_, whereas ([19], p. 248) uses _microfind_; the latter is correct while the former can lead to an infinite loop. Moreover it may be useful to point out that \(\textit{macrofind}(x)\) must return, as the \"name\" of the macroset containing \(x\), not an arbitrary member of that set, but the member which is closest to the root of the tree.) Algorithm 11 then runs in \(O(p+s)\) time and our solution as a whole in \(O(p+s+t)\) time. ## 3 Experimental Results and Discussion

We implemented the described solution in C++ as a working example of a solution with a linear time complexity. It is publicly available in an online repository ([[https://github.com/janezb/insertions](https://github.com/janezb/insertions)]([https://github.com/janezb/insertions](https://github.com/janezb/insertions)), accessed on 16 June 2025). It is a self-contained solution with no external dependencies. Note that the implementation was not optimized for speed so there should be plenty of room for improvements if the actual running time is of importance. All the experiments presented in this section were carried out on a desktop computer with a 3.2 GHz i9-12900K CPU and 64 GB of main memory; the source code was compiled with _clang_ 7.0.0 with all optimizations enabled (-03). In this section, we want to demonstrate the linearity of its time complexity and describe the behavior of the algorithm on different inputs that offers further insight into its design. Random data or actual text is unlikely to present an obstacle to any string counting approaches as mismatches occur quickly. This is shown in Table 1, which shows running times in seconds for a reasonably large choice of string lengths \(|p|=\) 200,000, \(|s|=\) 300,000, and \(|t|=\) 100,000. The strings are either randomly generated, substrings (constructed in two ways, on which see the next two paragraphs) of a longer English text, fragments of DNA sequences or of C++ source code, or substrings of a periodic string with a base period of length \(d\) (for various values of \(d\)). We can see that periodic strings provide the largest obstacle as they force the algorithm to execute all steps. (Defining the strings in this way means that there will be approx.