# Substring Counting with Insertions
## 2 Materials and Methods
### Distinguished Nodes  
We do not really need the values of \(f(i,j)\), which we calculated in the quadratic solution, for _all_ pairs \((i,j)\), but only for one such pair \((i_{k},j_{k})\) for each \(k\) (i.e., each possible position where \(t\) can be inserted into \(s\)), which is only \(O(s)\) values and not all \(O(p^{2})\). We will show how to compute those values of the function \(f\) that we really need, without computing all the others. Let us traverse the tree \(T_{\mathsf{P}}\) from the bottom up (from leaves towards the root) and compute the sizes of the subtrees; whenever we encounter a node \(u\) with its subtree (let us call it \(T_{u}\); it consists of \(u\) and all its descendants) of size at least \(\sqrt{p}\) nodes, we mark \(u\) as a distinguished node and cut off the subtree \(T_{u}\). Cutting it off means we will not count the nodes in it when we consider subtrees of \(u\)'s ancestors higher up in the tree. When we finally obtain to the root, we mark it as well, regardless of how many nodes are still left in the tree at that time. Algorithm 5 calculates, for each node \(u\), its nearest marked ancestor \(M[u]\); if \(u\) itself is marked, then \(M[u]=u\). Now we have at most \(\sqrt{p}\) marked nodes (because every time we marked a node, we also cut off least \(\sqrt{p}\) nodes from the tree, and the number of all nodes is \(|p|\)); and each node is less than \(\sqrt{p}\) steps away from its nearest marked ancestor (if it were \(\sqrt{p}\) or more steps away, some lower-lying ancestor of this node would have a subtree with at least \(\sqrt{p}\) nodes, and would therefore get marked and its subtree cut off). ```
procedureMark(\(u\)): (*Variable \(N\) counts the number of nodes in \(T_{u}\) reachable through unmarked descendants. *) \(N:=1\); for every child \(v\) of node \(u\): \(N:=N+\textsc{Mark}(v)\); if\(N\geq\sqrt{p}\) or \(u=0\) then\(M[u]:=u\); return \(0\); (*Mark \(u\). *) else\(M[u]:=-1\); return \(N\); (*Ummarked \(u\). *)  main call: Mark(0); (*Start at the root--node 0. *) (*Pass the information about the nearest marked ancestor down the tree to all unmarked nodes. (from parents to children)*) for\(u:=1\)to\(|p|-1\)do if\(M[u]<0\)then\(M[u]:=M[\mathrm{P}_{p}[u]]\);
```  
**Algorithm 5** Marking distinguished nodes  
We know that \(f(i,|p|)=0\) for every \(i\). For each marked \(i\), we can compute all values of \(f(i,j)\) for \(1\leq j<|p|\) from \(f(i,|p|)\); since there are at most \(\sqrt{p}\) marked nodes, this takes \(O(p\sqrt{p})\) time. Let us describe how we can answer each of the \(O(s)\) queries \((i_{k},j_{k})\) that we are interested in. The nearest marked ancestor of node \(i_{k}\) is \(M[i_{k}]\); since it is marked, we already know \(f(M[i_{k}],j)\) for all \(j\), i.e., also for \(j=j_{k}\), and since \(i_{k}\) lies in the tree \(T_{\mathrm{P}}\) at most \(O(\sqrt{p})\) steps below node \(M[i_{k}]\), we can calculate \(f(i_{k},j_{k})\) from \(f(M[i_{k}],j_{k})\) in at most \(O(\sqrt{p})\) steps. Since we have to do this for each query, it takes overall \(O(s\sqrt{p})\) time. To save space, we can solve queries in groups according to \(M[i_{k}]\); after we process all queries that share the same node \(M[i_{k}]\), we can forget the results \(f(M[i_{k}],j)\). Algorithm 6 presents the pseudocode of this approach to counting the occurrences of type (V). ```
(*Group queries \((i_{k},j_{k})\) based on the nearest marked ancestor. *) for\(u:=0\)to\(|p|-1\)do if\(M[u]=u\)then\(L[u]:=\) empty list; for\(k:=1\)to\(|s|-1\)do add \(k\) to \(L[M[i_{k}]]\); (*Process marked nodes \(u\). *) for\(u:=0\)to\(|p|-1\)do if\(M[u]=u\): (*Compute \(f(u,j)\) for all \(j\) as \(F[j]\). *) \(F[|p|]:=0\); for\(j:=|p|-1\) downto \(1\)do in \(F[j]\) store \(f(u,j)\) that is computed from \(f(u,\mathrm{S}_{p}[j])\), which is stored in \(F[\mathrm{S}_{p}[j]]\); (*Answer queries \((i_{k},j_{k})\), where \(u\) is the nearest marked ancestor of \(i_{k}\). *) for each\(k\)in\(L[u]\): (*Prepare the path in the tree from \(i_{k}\) to its ancestor \(u\).