# Substring Counting with Insertions
## 2 Materials and Methods
### Linear-Time Solution
All of these things can be prepared in advance (\(\ell_{1}\), \(\ell_{2}\) using the table \(O_{pt}\)) or computed in \(O(1)\) time (with a small constant number of computations of the longest common prefix or suffix). #### 2.6.3 Finding the Next Candidate Prefix (or Suffix)

In this subsection we describe step 3 of Algorithm 8 in more detail. The purpose of that step is to answer, in \(O(s+p)\) time, up to \(|s|-1\) queries (one for each position \(k\) where the string \(t\) may be inserted into \(s\)) of the form \"given a prefix \(u\) of \(p\), find the longest suffix of \(u\) that is shorter than \(|u|/2\) and is also a prefix of \(p\)\". We may describe such a query with a pair \((u_{k},b_{k})\), where \(u_{k}=|u|\) is the length of the original prefix and \(b_{k}=\lceil u_{k}/2\rceil-1\) is the maximum length of the new shorter prefix that we are looking for. [PERSON] and [PERSON] showed that this problem can be reduced to a weighted-ancestor problem in the suffix tree of \(p^{n}\) ([10], Lemma 2.2), for which they then provided a linear-time solution ([10], Section 4). However, this solution is quite complex and in the present subsection we will present a simpler alternative which avoids the need for weighted-ancestor queries. The longest suffix of \(p[:u_{k}]\) that is also a prefix of \(p\) has the length \(\mathsf{P}_{p}[u_{k}]\), the second longest has the length \(\mathsf{P}_{p}[\mathsf{P}_{p}[u_{k}]]\), and so on. We could examine this sequence until we reach an element that is \(\leq b_{k}\); that would be the answer to the query \((u_{k},b_{k})\). We can also imagine this procedure as climbing the tree \(T_{\mathsf{P}}\) (first introduced in Section 2.3), starting from the node \(u_{k}\) and proceeding upwards towards the root until we reach a node with the value \(\leq b_{k}\). However, we can save time by observing that several of these paths up the tree, for different queries, sometimes meet in the same node and thenceforth always move together. If several paths reach some node \(v\) and do not end there (because the bounds \(b_{k}\) of those queries are \(<v\)), all these paths will continue into \(v\)'s parent \(w:=\mathsf{P}_{p}[v]\) and will never separate again, regardless of where in \(v\)'s subtree they started. Thus, in a certain sense, we no longer need to distinguish between the nodes \(w\), \(v\), and \(v\)'s descendants, as the result of any query with \(b_{k}<v\) is the same regardless of which of these nodes its path begins in. We can imagine these nodes as having merged into one, namely into \(v\)'s parent \(w\). To follow the paths up the tree, we will visit the nodes of the tree in decreasing order, from \(|p|-1\) to \(0\). Upon reaching node \(v\), we can answer all queries whose bound is exactly \(b_{k}=v\), and then we can merge \(v\) with its parent, thereby taking into account the fact that all paths that reach \(v\) and do not end there will proceed to \(v\)'s parent. For every node \(w\) that has not yet been merged with its parent, we maintain a set of all nodes that have already been merged into \(w\); at the start of the procedure, each node forms a singleton set by itself. The pseudocode of this approach is shown in Algorithm 11. ```
1\(F:=\{\{0\},\{1\},\ldots,\{|p|-1\}\}\);
2 for\(v:=|p|-1\) downto \(0\):
3 foreach query \((u_{k},b_{k})\) having \(b_{k}=v\):
4 the answer to this query is the smallest element of that member of \(F\) which contains \(u_{k}\);
5 merge, in \(F\), the set containing \(v\) and the set containing \(\mathsf{P}_{p}[v]\);
```

**Algorithm 11** Answering a batch of queries \((u_{k},b_{k})\) in the KMP-tree \(T_{\mathsf{P}}\). The following invariant holds at the start of each iteration of the main loop: \(F\) contains one set \(A_{w}\) for each node \(w\in\{0,1,\ldots,v\}\), and this set \(A_{w}\) contains \(w\) as well as those children of \(w\) (in the tree \(T_{\mathsf{P}}\)) that are greater than \(v\), and all the descendants of those children.