# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
(3.2) Otherwise, if \(\kappa=|p|\), we see that for \(\alpha\leq\alpha^{\prime}_{\max}\), the string \(p\) (if it starts at position \(\alpha d\) in \(utv\)) lies entirely within the periodic part of \(utv\); since \(\kappa=|p|\) means that \(p\) is itself entirely periodic with the same period of length \(d\), we can conclude that, for each \(\alpha\) (from \(\alpha_{\min}\) to \(\alpha^{\prime}_{\max}\)), \(p\) matches completely with the corresponding part of \(utv\); thus there are \(\alpha^{\prime}_{\max}-\alpha_{\min}+1\) occurrences. (3.3) However, if \(\kappa<|p|\), we can reason very similarly as in case (2). At \(\alpha=\alpha^{\prime}_{\max}\) we have an occurrence of \(p[\kappa]\), which may or may not be extended to an occurrence of the whole \(p\); we check this with at most two calls of LCP. At \(\alpha=\alpha^{\prime}_{\max}\) the string \(p[\kappa]\) lies entirely within the periodic part of the string \(utv\); if we then decrease \(\alpha\) and thus shift \(p\) to the left by \(d\) or a multiple of \(d\) characters, then \(p[\kappa]\) will certainly also fall within the periodic part of the string \(utv\). In order for the entire \(p\) to occur at such a position, among other things, \(p[\kappa]\) and \(p[\kappa-d]\) would have to match with the corresponding characters of the string \(utv\), but since these two characters are both in the periodic part of the string \(utv\), they are equal, while the characters \(p[\kappa]\) and \(p[\kappa-d]\) are not equal (because \(p[\kappa]\) is the longest prefix of \(p\) with period \(d\)); therefore, a mismatch will definitely occur for every \(\alpha<\alpha^{\prime}_{\max}\) and \(p\) does not appear there. Step 2 of the GG algorithm can therefore be summarized by Algorithm 9. #### 2.6.2 Counting the Remaining Occurrences

Now let us consider step 7 of Algorithm 8. At that point in the GG algorithm, we have already truncated \(u\) and \(v\) so that they are shorter than \(|p|/4\). If \(|u|=0\) or \(|v|=0\) or \(|utv|<|p|\), we can immediately conclude that there are no relevant occurrences of \(p\). We can assume that \(|t|>|p|/2\), as otherwise the string \(utv\) would certainly be shorter than \(|p|\). We are interested in such occurrences of \(p\) in \(utv\) that start within \(u\) and end within \(v\); such an occurrence also covers the entire \(t\) in the middle. Candidates for a suitable occurrence of \(p\) in \(utv\) are therefore present only where \(t\) appears in \(p\) (more precisely: the fact that \(t\) occurs in \(p\) starting at \(\ell\) is a necessary condition for \(p\) to appear in \(utv\) starting at \(|u|-\ell\)). We compute in advance (using the table \(\mathsf{O}_{pt}\)) the index of the first and (if it exists) second occurrence of \(t\) as a substring in \(p\); let us call them \(\ell_{1}\) and \(\ell_{2}\). If there was just one occurrence of \(t\) in \(p\), then there is also just one candidate for the occurrence of \(p\) in \(utv\) and with two more calls of LCP we can check whether \(p\) really occurs there (i.e., whether \(p[\cdot\ell_{1}]\) is a suffix of \(u\) and \(p[\ell_{1}+|t|\colon]\) is a prefix of \(v\)). ```
\(\alpha_{\min}:=\max\{0,1+\lfloor(|u|+|t|-|p|)/d\rfloor\}\); \(\alpha_{\max}:=\lfloor\min\{|u|/2,|utv|-|p|\}/d\rfloor\); if\(\alpha_{\max}<\alpha_{\min}\)thenreturn\(0\); \(\kappa:=\) length of the longest prefix of \(p\) with a period \(d\); \(\lambda:=\) length of the longest common prefix of \(p[:\kappa]\) and \((utv)[\alpha_{\max}d.]\); if\(\lambda=\kappa\); if\(\kappa=|p|\)thenreturn\(\alpha_{\max}-\alpha_{\min}+1\) elseif\(p\) is a prefix of \((utv)[\alpha_{\max}d.]\)thenreturn\(1\) elsereturn\(0\); \(\alpha^{\prime}_{\max}:=\alpha_{\max}-\lceil(\kappa-\lambda)/d\rceil\); if\(\alpha^{\prime}_{\max}<\alpha_{\min}\)thenreturn\(0\) elseif\(\kappa=|p|\)thenreturn\(\alpha^{\prime}_{\max}-\alpha_{\min}+1\) elseif\(p\) is a prefix of \((utv)[\alpha^{\prime}_{\max}d.]\)thenreturn\(1\) elsereturn\(0\);
```
**Algorithm 9** Occurrences of \(p\) in \(utv\) that start within the left half of \(u\) and end within \(v\).