# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
The string \(u\) is a prefix of \(p\) and has a base period \(d\); perhaps there exists a longer prefix of \(p\) with this period; let \(p[:\!x]\) be the longest such prefix. We obtain it by finding the longest common prefix of the strings \(p\) and \(p[d\! :]\), i.e., \(\kappa=d+\textsc{lcp}(0,d)\). Let \(\lambda\) be the length of the longest common prefix of the strings \(p[:\!x]\) and \((utv)[\alpha_{\max}d\! :]\) (in other words, we are interested in whether \(p[:\!x]\) appears in \(utv\) starting at \(\alpha_{\max}d\); we already know that there is certainly no mismatch with \(u\), so at most two calls of lcp are enough to check whether everything matches with \(t\) and \(v\) or find where the first mismatch occurs). Then we know that the string \((utv)[:\!\alpha_{\max}d+\lambda]\) is periodic with the same period of length \(d\) as \(p[:\!x]\) and \(u\). An example is shown in Figure 3.

(1) If \(\lambda=\kappa=|p|\), we have found a suitable occurrence of \(p\), and since \(utv\) has a period of \(d\) until the end of this occurrence, this means that if we were now to shift \(p\) in steps of \(d\) characters to the left and then compare it with the same part of \(utv\), we would see exactly the same substring in \(utv\) after each such shift as before, i.e., we would also find occurrences of \(p\) in all these places. In this case, all \(\alpha\) from \(\alpha_{\min}\) to \(\alpha_{\max}\) are suitable, so we have found \(\alpha_{\max}-\alpha_{\min}+1\) occurrences. (2) If \(\lambda=\kappa<|p|\), we have found an occurrence of \(p[:\!x]\) in \(utv\) starting at \(\alpha_{\max}d\). This occurrence of \(p[:\!x]\) may or may not continue into an occurrence of the entire \(p\); this can be checked with at most two more calls of lcp. As for possible occurrences further to the left, i.e., starting at \(\alpha d\) for some \(\alpha<\alpha_{\max}\); in such an occurrence, \(p[\kappa]\) should match with

Figure 3: The reach of the base period \(d\) at the beginnings of the sequences \(utv\) and \(p\). Figure 2: The periodicity of \(u\) when \(p\) occurs in the first half. the character \((utv)[\alpha d+\kappa]\), which is still in the periodic part of \(utv\) (\(ad+\kappa<\alpha_{\max}d+\lambda\)), i.e., it is equal to the character \(d\) places further to the left, which in turn must be equal to the character \(p[\kappa-d]\). So \(p[\kappa]\) and \(p[\kappa-d]\) should be the same, but they certainly are not, because then the periodic prefix of \(p\) (with period \(d\)) would be at least \(\kappa+1\) characters long, not just \(\kappa\) characters. Thus, we see that for \(\alpha<\alpha_{\max}\) there is definitely a mismatch and \(p\) does not occur there. (3) If \(\lambda<\kappa\), we have a mismatch between \(p[\lambda]\) and \((utv)[\alpha_{\max}d+\lambda]\). We did not find an occurrence of \(p\) at \(\alpha_{\max}d\), but what about \(ad\) for smaller values of \(\alpha\)? If we now move \(p\) left in steps of \(d\), the same character of the string \(utv\) will have to match \(p[\lambda+d]\), \(p[\lambda+2d]\), and so on. As long as these indices are smaller than \(\kappa\), all these characters are equal to the character \(p[\lambda]\), since this part of \(p\) is periodic with period \(d\); therefore, a mismatch will occur for them as well. In general, if \(p\) starts at \(\alpha d\), the character \((utv)[\alpha_{\max}d+\lambda]\) will have to match \(p[(\alpha_{\max}-\alpha)d+\lambda]\); a necessary condition to avoid the aforementioned mismatch is therefore \((\alpha_{\max}-\alpha)d+\lambda\geq\kappa\) or \(\alpha\leq\alpha_{\max}-\lceil(\kappa-\lambda)/d\rceil\). Thus, we have obtained a new, tighter upper bound for \(\alpha\), which we will call \(\alpha^{\prime}_{\max}\). For \(\alpha\leq\alpha^{\prime}_{\max}\), the string \(p[\kappa]\) lies entirely within the periodic part of the string \(utv\), i.e., within \((utv)[\alpha_{\max}d+\lambda]\). (3.1) If \(\alpha^{\prime}_{\max}<\alpha_{\min}\), we know that there is no possible \(\alpha\) and we will not find an occurrence of \(p\) here.