# Substring Counting with Insertions
## 2 Materials and Methods
### Quadratic Solution
To check whether some \(p[\ell:]\) is a prefix of \(p[j:]\), we only have to check if \(\sigma_{\mathsf{S}}[\ell]\leq\sigma_{\mathsf{S}}[j]\leq\tau_{\mathsf{S}}[\ell]\). (Another way to check whether \(p[\ell:]\) is a prefix of \(p[j:]\) is with the \(Z\)-algorithm ([7], pp. 7-10). For any string \(w\), we can prepare a table \(\mathsf{Z}_{w}\) in \(O(w)\) time, where the element \(\mathsf{Z}_{w}[i]\) (for \(i=0,\ldots,|w|\)) tells us the length of the longest common prefix of the strings \(w\) and \(w[i:]\). The question we are interested in--i.e., whether \(p[\ell:]\) is a prefix of \(p[j:]\)--is equivalent to asking whether \(p[\ell:]=p[j:j+|p|-\ell]\), which is equivalent to \(p^{\mathsf{R}}[:|p|-\ell]=p^{\mathsf{R}}[\ell-j:|p|-j]\), and hence to the question whether \(p^{\mathsf{R}}\) and \(p^{\mathsf{R}}[\ell-j:]\) match in the first \(|p|-\ell\) characters, i.e., whether \(\mathsf{Z}_{p^{\mathsf{R}}}[\ell-j]\geq|p|-\ell\). However, for our purposes the tree-based solution is more useful than the one using the \(Z\)-algorithm, as we will later use the tree in solutions with a lower time complexity than the quadratic one that we are describing now.) Our procedure so far (Algorithm 3) has computed \(f(i,j)\) by checking whether \(p\) occurs at the beginning of \(p[:i]\)\(t\)\(p[j:]\) and handling subsequent occurrences via \(f(i^{\prime},j)\) for \(i^{\prime}=\mathsf{P}_{p}[i]\). Of course, we could also go the other way: we would first check whether \(p\) occurs at the end (instead of the beginning) of \(p[:i]\)\(t\)\(p[j:]\) and then add earlier occurrences via \(f(i,j^{\prime})\) for \(j^{\prime}=\mathsf{S}_{p}[j]\). To check if \(p\) occurs at the end of \(p[:i]\)\(t\)\(p[j:]\), we should first check whether \(t\) occurs in \(p\) at indices from \(j-|t|\) to \(j\) (with the same table as before in line 3), and then we would be interested in whether \(p[:i]\) ends with \(p[:j-|t|]\). Here, it would be helpful to construct a tree \(T_{\mathsf{P}}\), which would have one node for each \(u\) from \(0\) to \(|p|-1\); node \(0\) would be the root, and for every \(u>0\), the node \(u\) would be a child of node \(\mathsf{P}_{p}[u]\). Using the procedure Preorder on this tree would give us tables \(\sigma_{\mathsf{P}}\) and \(\tau_{\mathsf{P}}\). We should then check whether \(j-|t|\) is an ancestor of node \(i\) in the tree. ```
procedureTraverse(tree \(T\), node \(u\),  tables \(\sigma\) and \(\tau\), index \(i\)): \(i:=i+1\); \(\sigma[u]:=i\); for every child \(v\) of node \(u\) in tree \(T\): \(i:=\textsc{Traverse}(T,v,\sigma,\tau,i)\); \(\tau[u]:=i\); return\(i\); procedurePreorder(input: tree \(T\);  output: tables \(\sigma\) and \(\tau\)):  let \(\sigma\) and \(\tau\) be tables with indices from \(1\) to \(|p|\); \(\textsc{Traverse}(T,\text{root of }T,\sigma,\tau,0)\); return\(\sigma,\tau\); main call: \(\sigma_{\mathsf{S}},\tau_{\mathsf{S}}:=\textsc{Preorder}(T_{\mathsf{S}})\);
```  
**Algorithm 4** Tree traversal for determining the ancestor-descendant relationships  
Thus, we see that we can compute \(f(i,j)\) quickly, in \(O(1)\) time, either from \(f(\mathsf{P}_{p}[i],j)\) or from \(f(i,\mathsf{S}_{p}[j])\); both ways will come in handy later. Our current procedure for computing the function \(f\) would take \(O(p)\) time to prepare trees \(T_{\mathsf{P}}\) and \(T_{\mathsf{S}}\) and tables \(\sigma_{\mathsf{P}}\), \(\sigma_{\mathsf{S}}\), \(\tau_{\mathsf{P}}\) and \(\tau_{\mathsf{S}}\), followed by \(O(p^{2})\) time to calculate the value of \(f(i,j)\) for all possible pairs \((i,j)\). This solution has a time complexity of \(O(s+t+p^{2})\).