# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
Now suppose that there are at least two occurrences of \(t\) in \(p\). Let us consider some occurrence of \(p\) in \(utv\) (of course one that starts within \(u\) and ends within \(v\)); the string \(t\) in \(utv\) matches one of the occurrences of \(t\) in \(p\); let \(\ell\) be the position where this occurrence of \(t\) in \(p\) begins (Figure 4). There are at most \(|u|\) characters to the left of this occurrence of \(t\) in \(p\) (otherwise \(p\) would already extend beyond the left edge of \(utv\)), and there are at most \(|v|\) characters to the right of it (otherwise \(p\) would extend beyond the right edge of \(utv\)). Therefore, no other occurrence of \(t\) in \(p\) can begin more than \(|u|\) characters to the left of \(\ell\) or more than \(|v|\) characters to the right of \(\ell\). If another occurrence of \(t\) in \(p\) begins at position \(\ell^{\prime}\), then \(|\ell-\ell^{\prime}|\leq\max\{|u|,|v|\}<|p|/4\). Since no occurrence of \(t\) in \(p\) is very far from \(\ell\), it follows that the first two occurrences of \(t\) in \(p\) (i.e., those at \(\ell_{1}\) and \(\ell_{2}\)) cannot be very far from each other. We can verify this as follows: (1) if the occurrence of \(t\) in \(p\) at \(\ell\) was exactly the first occurrence of \(t\) in \(p\) (i.e., if \(\ell=\ell_{1}\)), it follows that \(\ell_{2}\) is greater than \(\ell=\ell_{1}\) by at most \(|v|\), so \(\ell_{2}-\ell_{1}\leq|v|<|p|/4\); (2) if the occurrence of \(t\) in \(p\) at \(\ell\) was not the first occurrence of \(t\) in \(p\), but the second or some later one (that is, if \(\ell\geq\ell_{2}\)), it follows that \(\ell_{1}\) and \(\ell_{2}\) are both less than or equal to \(\ell\), but by at most \(|u|\), so again \(\ell_{2}-\ell_{1}\leq|u|<|p|/4\). We see that if \(p\) occurs in \(utv\) (starting within \(u\) and ending within \(v\)), the first two occurrences of \(t\) in \(p\) are less than \(|p|/4\) apart. So, we can start by computing \(d:=\ell_{2}-\ell_{1}\) and if \(d\geq|p|/4\), we can immediately conclude that we will not find, in \(utv\), any occurrences of \(p\) that start within \(u\) and end within \(v\). Otherwise, we know henceforth that \(d<|p|/4<|t|/2\), so the first two occurrences of \(t\) in \(p\) overlap by more than half; the overlapping part is, therefore, both a prefix and a suffix of \(t\), say \(t=t_{1}t_{2}=t_{2}t_{3}\) for \(|t_{1}|=|t_{3}|=d\) and \(|t_{2}|>|t|/2\); so \(t\) is periodic with a period of length \(d<|t|/2\). Now suppose that \(t\) has some shorter period \(d^{\prime}\). If \(0\leq t<|t|-d^{\prime}\), the characters \(p[\ell_{1}+i]\) and \(p[\ell_{1}+d^{\prime}+i]\) both lie in the first occurrence of \(t\) in \(p\), so they are equal since \(t\) has period \(d^{\prime}\); if \(|t|-d^{\prime}\leq t<|t|\), then both of these characters lie in the second occurrence of \(t\) in \(p\) and are therefore equal. Since this is true for all \(0\leq t<|t|\), we have found another intermediate occurrence of \(t\) in \(p\) starting at \(\ell_{1}+d^{\prime}\), which contradicts

Figure 4: The alignment of string \(t\) with string \(p\) at an occurrence of \(p\) in \(utv\). the assumption that the second occurrence is the one at \(\ell_{2}\). Thus, \(d\) is the shortest period of \(t\). Consider the first occurrence of \(t\) in \(p\), the one starting at \(\ell_{1}\), and see how far left and right of it we could extend \(t\)'s period of length \(d\); that is, we need to compute the longest common suffix of the strings \(p[:\ell_{1}]\) and \(p[:\ell_{1}+d]\), and the longest common prefix of the strings \(p[\ell_{1}+|t|-d:]\) and \(p[\ell_{1}+|t|:]\). Now we can imagine \(p\) partitioned into \(p=p_{1}p_{2}p_{3}\), where \(p_{2}\) is the maximal substring that contains that occurrence of \(t\) and has a period \(d\). Similarly, in \(utv\), let us see how far into \(u\) and \(v\) the middle part of \(t\) could be extended while maintaining periodicity with period \(d\).