# Substring Counting with Insertions
## 2 Materials and Methods
### Geometric Interpretation  
We want to count those occurrences of \(p\) in \(p[:i]\,t\,p[:]\) that start within \(p[:i]\) and end within \(p[j:]\) (Figure 1). Such an occurrence is therefore of the form \(p=p[:\ell]\,t\,p[\ell+|t|:]\), where \(0<\ell\leq i,j\leq\ell+|t|<|p|\), and the following three conditions apply: (_a_) \(p[:\ell]\) must be a suffix of \(p[:i]\), (_b_) \(p[\ell+|t|:]\) must be a prefix of \(p[:]\), and (_c_) \(t\) must appear in \(p\) as a substring starting at index \(\ell\), i.e., \(t=p[\ell:\ell+|t|]\). To check (_c_), we prepare the table \(\mathsf{O}_{pt}\) in advance and check whether \(\mathsf{O}_{pt}[\ell]=1\). Let us now consider the condition (_a_), i.e., that \(p[:\ell]\) must be a suffix of \(p[:i]\). We know that the longest prefix of \(p\) that is also a suffix of \(p[:i]\) is \(\mathsf{P}_{p}[i]\) characters long; the second longest is \(\mathsf{P}_{p}[\mathsf{P}_{p}[i]]\) characters long, and so on. The condition that \(p[:\ell]\) must be a suffix of \(p[:i]\) essentially asks whether \(\ell\) occurs somewhere in the sequence \(i,\mathsf{P}_{p}[i],\mathsf{P}_{p}[p_{i}],\ldots\). This is equivalent to asking whether \(\ell\) is an ancestor of \(i\) in the tree \(T_{\mathsf{P}}\), which, as we have already seen, can be checked with the condition \(\sigma_{\mathsf{P}}[\ell]\leq\sigma_{\mathsf{P}}[i]\leq\tau_{\mathsf{P}}[\ell]\). Similar reasoning holds for condition (_b_), i.e., that \(p[\ell+|t|:]\) must be a prefix of \(p[:]\), except that now instead of the table \(\mathsf{P}_{p}\) and the tree \(T_{\mathsf{P}}\) we use the table \(\mathsf{S}_{p}\) and the tree \(T_{\mathsf{S}}\). The condition (_b_) asks whether \(\ell+|t|\) is an ancestor of \(j\) in the tree \(T_{\mathsf{S}}\), which can be checked with \(\sigma_{\mathsf{S}}[\ell+|t|]\leq\sigma_{\mathsf{S}}[j]\leq\tau_{\mathsf{S}}[ \ell+|t|]\). The two inequalities we have thus obtained,  
\[\sigma_{\mathsf{P}}[\ell]\leq\sigma_{\mathsf{P}}[i]\leq\tau_{\mathsf{P}}[\ell ]\quad\text{and}\quad\sigma_{\mathsf{S}}[\ell+|t|]\leq\sigma_{\mathsf{S}}[j] \leq\tau_{\mathsf{S}}[\ell+|t|],\]  
have a geometric interpretation which will prove useful: if we think of \(\sigma_{\mathsf{P}}[i]\) and \(\sigma_{\mathsf{S}}[j]\) as the \(x\)- and \(y\)-coordinates, respectively, of a point on the two-dimensional plane, then the two inequalities require the \(x\)-coordinate to lie on a certain range and the \(y\)-coordinate to lie within a certain other range; in other words, the point must lie within a certain rectangle. Recall that \(i\) and \(j\) depend on the position \(k\) where the string \(t\) has been inserted into \(s\); therefore, to avoid confusion, we will now denote them by \(i_{k}\) and \(j_{k}\). We will refer to the point from the previous paragraph as \(Q_{k}:=(\sigma_{\mathsf{P}}[i_{k}],\sigma_{\mathsf{S}}[j_{k}])\), and to the rectangle as \(R_{\ell}:=[\sigma_{\mathsf{P}}[\ell],\tau_{\mathsf{P}}[\ell]]\times[\sigma_{ \mathsf{S}}[\ell+|t|],\tau_{\mathsf{S}}[\ell+|t|]]\). Thus, we now see that \(p\) occurs in \(s[:k]\,t\,s[k:]\) such that the occurrence of \(t\) at position \(\ell\) of \(p\) aligns with the occurrence of \(t\) at position \(k\) of \(s[:k]\,t\,s[k:]\) if and only if \(Q_{k}\) lies in \(R_{\ell}\). Actually we are not interested in whether a match occurs for a particular \(k\) and \(\ell\), but in how many occurrences there are for a particular \(k\); in other words, for each \(k\) (from \(1\) to \(|s|-1\)) we want to know how many rectangles \(R_{\ell}\) contain the point \(Q_{k}\). Here \(\ell\) ranges over all positions where \(t\) appears as a substring in \(p\) (i.e., where \(p[\ell:\ell+|t|]=t\) or, equivalently, \(\mathsf{O}_{pt}[\ell]=1\)); by limiting ourselves to such \(\ell\), we also take care of condition (_c_). Thus, we have \(O(s)\) points and \(O(p)\) rectangles, and for each point we are interested in how many of the rectangles contain it.