# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
For \(|p|<|t|\), no part of Algorithm 8 needs to be executed and only the \"everything else\" category remains. For \(|p|>4|s|\), steps 1-6 of Algorithm 8 do not need to be executed, which also means we do not have to initialize the union-find data structure; we still need to preprocess \(p\) to support constant-time LCP queries, however, since these are needed in step 7. The size of the input to our algorithm is defined by three variables--the lengths of the strings \(p,s\), and \(t\). We can show the behavior of the algorithm by fixing one variable to a reasonable value and observing the 3D chart of the running time as a function of the other two variables. In Figure 9, we can observe approximately plane-shaped charts, demonstrating that the running time is linear in the lengths of the input strings. ## 4 Conclusions

We investigated the problem of computing the number of occurrences of substring \(p\) in all possible insertions of string \(t\) into string \(s\). We have presented four solutions with different time complexities and based on different techniques. Somewhat surprisingly, the problem can be solved with an algorithm that has linear time complexity \(O(|s|+|t|+|p|)\) and is based on an adaptation of a recent result from the field of string finding in a compressed text. The algorithm is thoroughly explained. An implementation in C++ of the described solution is publicly available. Figure 8: Running time of individual parts of the algorithm, for \(|s|=\) 300,000, \(|t|=\) 1,000,000, and various lengths \(|p|\). Figure 9: Plots of running times (shown in seconds on the \(z\)-axis) when the length of one of the strings \(s\), \(t\), \(p\) is fixed at 300,000 while the length of the other two strings varies. Results are shown only for those combinations of \(|s|\), \(|t|\), \(|p|\) where \(|t|<|p|\leq|s|+|t|\) and where all three lengths are \(\leq\)10\({}^{6}\). We encountered some interesting problems that we were unable to solve. In the geometric solution using a plane sweep, the rectangles are neatly nested in individual dimensions. Projections of rectangles onto coordinate axes are a set of segments, where for every two segments, one is completely contained in the other, or the segments do not intersect. This is an obvious consequence of the fact that each rectangle corresponds to a node or subtree. We have not been able to exploit these properties in our solution. The second open problem is a simplification of the GG algorithm. The basic result from which our solution is derived was developed for string searching in different concatenations of three substrings of the same string. In our problem, however, we are dealing with inserting one string into all possible places in the other string. As we have shown, we can reduce the problem to searching for a string \(p\) in concatenations of a prefix of the string \(p\), the entire string \(t\), and a suffix of the string \(p\). For this specific case, further simplifications may be possible. Conceptualization, methodology, investigation, formal analysis, validation, resources, writing--review and editing, J.B. and T.H. ; software, writing--original draft preparation, visualization, J.B.; supervision, project administration, T.H. All authors have read and agreed to the published version of the manuscript. This study was supported by the research programmes P2-0103 and P2-0209 of the Slovenian Research and Innovation Agency. The software implementation of the presented algorithm is openly available at [[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. The authors would like to thank [PERSON] for sharing their results in the field of string searching in compressed texts, which led to a linear solution to the problem. The authors declare no conflicts of interest. ## References

* (1) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Exact string matching algorithms: Survey, issues, and future research directions.