# Substring Counting with Insertions
## 1 Introduction  
Substring search is one of the classical algorithmic problems, which has a somewhat surprising linear-time solution. However, there is an abundance of algorithms that address the same or similar problems [1]. In this paper, we focus on a new version of the problem, where we are dealing with a changing string in which we are searching for a substring. We are given strings \(s\), \(t\), and \(p\). We will denote the length of the string \(s\) as \(|s|\). If we _insert_\(t\) into \(s\) at position \(k\) (where \(0\leq k\leq|s|\)), we obtain a new string that is formed by the first \(k\) characters of string \(s\), followed by the entire string \(t\) and concluded by the remaining \(|s|-k\) characters of \(s\). We want to count the number of occurrences of \(p\) as a substring in every string that can be obtained with the insertion of \(t\) into \(s\) at all possible positions \(k\). We make no assumption regarding the lengths of the input strings. They may be potentially millions of characters long; they may be comparable in length, or some may be much shorter than others. The only constraint is that \(s\) and \(t\) together should not be shorter than \(p\), as that would make the problem trivial. For example, if we insert \(t=\texttt{aba}\) into \(s=\texttt{ab}\) at position \(k=0\), we get abaab. For insertions at \(k=1\) and \(k=2\) we get abab and ababa, respectively. If we are interested in occurrences of \(p=\texttt{aba}\), we will find two when inserting \(t\) into \(s\) at \(k=2\): ababa and ababa (occurrences can of course overlap). The problem can be solved trivially by employing any substring counting algorithm with a linear time complexity on all \(|s|+1\) strings obtained by inserting \(t\) into \(s\). However, we are interested in more efficient solutions that do not have a quadratic time complexity in terms of the length of string \(s\), which we are modifying and searching the substring in. The paper presents different approaches to solving the problem in the following sections from less to more computationally efficient. Some approaches are improvementsof the previous ones while others exploit different properties. We first establish some preliminaries, which are used throughout the rest of the paper. Then we describe a solution with time complexity that is quadratic in terms of the length of the pattern string \(p\) but linear in the length of the strings \(s\) and \(t\). We achieve this through the use of similarities between the problems of counting the same pattern string \(p\) in strings that are a result of inserting \(t\) into \(s\) in adjacent locations. The following chapter improves this solution with a precomputation that gives us a solution with subquadratic time complexity. Next, we focus on a different, geometric interpretation of a problem, which reorders the computation of solutions to the \(|s|+1\) problems and achieves a time complexity of \(O(t+(p+s)\log p)\). It is based on reducing the problem to the point location problem, more precisely to rectangle stabbing or dynamic interval stabbing [2,3]. Finally, we present a solution with a linear time complexity \(O(s+t+p)\), which is based on a recent result [4] on finding substrings in a compressed text [5]. This paper presents a theoretical result in string processing: a worst-case linear-time algorithm that generalizes the classical string matching problem. Specifically, instead of computing pattern occurrence counts in a single, fixed text, our algorithm efficiently computes such counts across a linear number of systematically modified texts, all within the same asymptotic time bound. We outline some potential areas of application for the developed algorithms. In bioinformatics, pattern counting is fundamental to genome sequence analysis, where the patterns of interest may correspond to known biological motifs or regulatory elements. The inserted sequences can represent indels or longer structural variants. They could also originate from viruses that are able to insert their genetic material into host chromosomes.