# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
\(O(|s|/d)\) positions \(k\) where \(t\) may be inserted into \(s\) without \"disrupting\" its period, and for every such \(k\) the string \(t\) in \(s[:k]\,\



(occurring every \(d\) characters), none of the checks in the first few lines of Algorithm 10 succeed in terminating it early, and so it has to be executed in full.) For \"English text 1\", we extracted the letters (converted to lowercase) from an English-language document, resulting in a long string \(w\); we then used the first \(|s|\) characters of \(w\) to form the string \(s\), the next \(|t|\) characters to form \(t\), and the next \(|p|\) characters to form \(p\). Since the strings are long, \(t\) is not a substring of \(p\) and running time is very short, similar to the case of purely random binary strings. For \"English text 2\", we selected \(p\) as a random substring (of length \(|p|\)) of \(w[:|st|]\), then selected \(t\) as a random substring (of length \(|t|\)) of \(p\); those parts of \(w[:|st|]\) which did not end up in \(t\) were then used to form \(s\). This ensures that \(t\) is a substring of \(p\) and \(p\) does occur (once) in one string of the form \(s[:k]\,t\,s[:k]\), so that the GG algorithm does need to be executed; but that is the only value of \(k\) for which \(u\) and \(v\) are of nontrivial length; even there, however, they cannot both be longer than \(|p|/4\) since \(p\) itself is only twice as long as \(t\). Accordingly, only one of \(u\) and \(v\) is ever longer than \(|p|/4\), so that only one of the loops 1-3 and 4-6 in Algorithm 8 needs to be executed and some running time is saved by not having to initialize the union-find data structure for the loop that does not need to be executed. For the \"DNA sequences\" and \"C++ source code\" rows in the table, we generated the strings \(s\), \(t\), and \(p\) in the same way as for \"English text 2\", except that the initial string \(w\) was obtained differently. For the DNA sequences, we used as \(w\) a DNA sequence of the yeast _Saccharomyces cerevisiae_ (the sequence was obtained from The Saccharomyces Genome Database project (SGD--[[https://www.yeastgenome.org/](https://www.yeastgenome.org/)]([https://www.yeastgenome.org/](https://www.yeastgenome.org/)), accessed on 18 June 2025) that hosts the data files of the _S. cerevisiae_ strain S288C. More specifically, we used the sequence of chromosome 4 of the release R64-4-1 ([[http://sgd-archive.yeastgenome.org/sequence/S2](http://sgd-archive.yeastgenome.org/sequence/S2)]([http://sgd-archive.yeastgenome.org/sequence/S2](http://sgd-archive.yeastgenome.org/sequence/S2)) 88C_reference/NCBI_genome_source/chr04.fsa, accessed on 18 June 2025) for C++ source code, and we obtained \(w\) by concatenating the files in the include directory of the C++ standard library as distributed with Microsoft Visual Studio. As expected, both of these kinds of strings behave similarly to the English text for the purposes of this experiment. All reported time measurements in Table 1 are averages and standard deviations over 100 runs (the later experiments in the rest of this section will show averages over 10 runs). For the \"same strings\" column, the same triple of strings \((s,t,p)\) was used in all the runs, while for the \"different strings\" column a different triple was generated for each run, according to the rules of the corresponding row (for the \"English text 1\", this means that the initial \(w\) from which \(s\), \(t\), and \(p\) are generated was obtained as a random substring of length \(|s|+|t|+|p|\) from a longer sequence of English-language text). Comparing the results in the two columns shows that the measurements are fairly robust both with regard to