# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
From these inequalities, we can now determine the smallest and largest acceptable value of \(\alpha\) (\(\alpha_{\min}\) and \(\alpha_{\max}\)). If \(\alpha_{\min}>\alpha_{\max}\), we can immediately conclude that there are no relevant occurrences of \(p\). Otherwise, if \(p_{1}\) and \(p_{3}\) are empty strings, then \(p=p_{2}\) and for every \(\alpha\) (from \(\alpha_{\min}\) to \(\alpha_{\max}\)) \(p_{2}\) lies within \(u_{2}tv_{1}\), so there are no mismatches; then we have \(\alpha_{\max}-\alpha_{\min}+1\) occurrences. If \(p_{3}\) is not empty, we can check the case \(\alpha=\alpha_{\min}\) separately (i.e., we check whether \(p\) appears in \(utv\) starting at \(|u|-\ell_{1}-\alpha_{\min}d\); we need at most two calls of lcp). What about larger \(\alpha\)? If we go from \(\alpha_{\min}\) to some larger \(\alpha\), the string \(p\) moves by \(d\) or a multiple of \(d\) characters to the left relative to \(utv\); this moves \(p[|p_{1}p_{2}|]=p_{3}[0]\), (i.e., the first character of the string \(p_{3}\)) so far to the left that its corresponding character of \(utv\) (with which the first character of the string \(p_{3}\) will have to match if \(p\) is to occur at the current position in \(utv\)) belongs to the periodic part (i.e., \(u_{2}tv_{1}\)); in addition, recall that (if the new \(\alpha\) is still valid at all, i.e., \(\leq\alpha_{\max}\)) the string \(p_{2}\) also overlaps with \(u_{2}tv_{1}\) by more than one whole period, so the character \(p[|p_{1}p_{2}|-d]=p_{2}[-d]\) is still in such a position that its corresponding character in \(utv\) is in the periodic part of \(u_{2}tv_{1}\); so here we have two characters in \(u_{2}tv_{1}\) that are exactly \(d\) places apart, hence they are equal. The first character of \(p_{3}\) cannot be equal to the character \(d\) places to the left of it, because otherwise the periodic part of \(p\), i.e., \(p_{2}\), could be expanded even further to the right and this character would not belong to \(p_{3}\) but instead to \(p_{2}\). We see that it is impossible that, in the new position of \(p\), the character \(p[|p_{1}p_{2}|]\) and the one \(d\) places to the left of it would match with the corresponding characters of \(utv\); there will be a mismatch in at least one place, so \(p\) can not occur there. Thus, we do not need to consider the case \(\alpha>\alpha_{\min}\) at all. The remaining possibility is that \(p_{3}\) is empty, but \(p_{1}\) is not empty. An analogous analysis to the previous paragraph tells us that it is sufficient to check whether \(p\) occurs in \(utv\) at \(\alpha=\alpha_{\max}\), and we do not need to consider smaller values of \(\alpha\). Thus, step 7 of the GG algorithm can be described with the pseudocode of Algorithm 10. ```
\(\ell_{1},\ell_{2}:=\) positions of the first two occurrences of \(t\) in \(p\); if there is only one occurrence thenreturn \(1\) or \(0\),  depending on whether \(p\) occurs in \(utv\) at position \(|u|-\ell_{1}\) or not; \(d:=\ell_{2}-\ell_{1}\); if\(d\geq|p|/4\)thenreturn \(0\);  partition \(p\) into \(p_{1}p_{2}p_{3}\), where \(p_{2}\) is the maximal substring that  contains the first occurrence of \(t\) in \(p\) and has period \(d\);  partition \(utv\) into \(u_{1}u_{2}tv_{1}v_{2}\), where \(u_{2}tv_{1}\) is the maximal substring  containing \(t\) between \(u\) and \(v\) and has period \(d\);  compute \(\alpha_{\min}\) and \(\alpha_{\max}\) from the aforementioned inequalities; if\(\alpha_{\min}>\alpha_{\max}\)thenreturn \(0\) elseif\(p_{3}\) is nonemptythenreturn \(1\) or \(0\),  depending on whether \(p\) appears in \(utv\) at position \(|u|-\ell_{1}-\alpha_{\min}d\) or not elseif\(p_{1}\) is nonemptythenreturn \(1\) or \(0\),  depending on whether \(p\) appears in \(utv\) at position \(|u|-\ell_{1}-\alpha_{\max}d\) or not elsereturn\(\alpha_{\max}-\alpha_{\min}+1\);
```
**Algorithm 10** Occurrences of \(p\) in the shortened string \(utv\).