# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
In step 3, we want to discover for some substring of \(p\) (namely the right half of the current \(u\), which was a prefix of \(p\)) how long is the longest suffix of this substring that is also a prefix of \(p\); we do not know how to do this in \(O(1)\) time, but we can solve \(O(s)\) such problems as a batch in \(O(s+p)\) time, which is good enough for our purposes, since we know that we will have to execute the GG algorithm for \(O(s)\) pairs \((u,v)\). (For details of this step, see Section 2.6.3.) Steps 4-6 are just a mirror image of steps 1-3 and the same considerations apply to them; that loop also makes at most two iterations. (Furthermore, note that steps 3 and 6 ensure that no occurrence of \(p\) is counted more than once: for example, those counted in step 2 all start within the left half of \(u\), and this is immediately cut off in step 3, so these occurrences do not appear again, e.g., in step 5). In step 7, we then know that \(u\) and \(v\) are shorter than \(|p|/4\); if \(utv\) is longer than \(p\), then \(t\) must be at least \(|p|/2\) characters long and we can make use of this when counting occurrences of \(p\) in \(utv\); we will look at the details in Section 2.6.2. As we will see, steps 2 and 7 each take \(O(1)\) time; the GG algorithm can therefore be executed \(O(s)\) times in \(O(s+p)\) time, and \(O(s+t+p)\) time is spent on preprocessing the data, so we have a solution with a linear time complexity. ```
algorithmGG(\(u,v\)): input: two strings, \(u\) (a prefix of \(p\)) and \(v\) (a suffix of \(p\)); output: the number of occurrences of \(p\) in \(utv\) that start within \(u\) and end within \(v\);
1 while\(|u|\geq|p|/4\);
2 count occurrences of \(p\) in \(utv\) that start within the left half of \(u\) (at positions \(\iota\leq|u|/2\)) and end within \(v\);
3\(u:=\) the longest suffix of the current \(u\) that is shorter than \(|u|/2\) and is also a prefix of \(p\);
4 while\(|v|\geq|p|/4\);
5 count occurrences of \(p\) in \(utv\) that start within \(u\) and end within the right half of \(v\) (at most \(|v|/2\) characters before the end of \(v\));
6\(v:=\) the longest prefix of the current \(v\) that is shorter than \(|v|/2\) and is also a suffix of \(p\);
7 count all occurrences of \(p\) in the current string \(utv\);

#### 2.6.1 Counting Early and Late Occurrences

Let us now consider step 2 of Algorithm 8 in more detail. The main idea will be as follows: we will find the base period of the string \(u\); calculate how far this period extends from the beginning of strings \(utv\) and \(p\); and discuss various cases of alignment with respect to the lengths of these periodic parts. We are, then, interested in occurrences of \(p\) in \(utv\) that begin at some position \(\iota\leq|u|/2\). Since \(u\) is also a prefix of \(p\), the occurrence of \(u\) at the beginning of \(p\) overlaps by at least one half with that at the beginning of \(utv\) (Figure 2). So \(u\)'s suffix of length \(|u|-\iota\) is also its prefix; therefore, \(u\) has a period of length \(\iota\); and since the length of this period is at most \(|u|/2\), it must be a multiple of the base period. Let us denote the base period by \(d\) (represented by the arcs under the strings in Figure 2); recall that it can be computed as \(|u|-\mathrm{P}_{p}[|u|]\). We need to consider only positions of the form \(\iota=\alpha d\) for integer \(\alpha\); the lower bound for \(\alpha\) is obtained from the conditions \(\iota\geq 0\) and \(\iota+|p|>|ut|\) (so that the occurrence of \(p\) ends within \(v\) and not sooner), and the upper bound from the conditions \(\iota\leq|u|/2\) (so that the occurrence of \(p\) begins within the first half of \(u\)) and \(\iota+|p|\leq|utv|\) (so that the occurrence of \(p\) does not extend beyond the end of \(utv\)). Let us call these bounds \(\alpha_{\min}\) and \(\alpha_{\max}\). If \(\alpha_{\min}>\alpha_{\max}\), we can immediately conclude that no appropriate occurrence of \(p\) exists.