# Substring Counting with Insertions
## 2 Materials and Methods  
### Preliminaries  
We will denote the length of the string \(x\) by \(|x|\), except in the big O notation \(O(\cdot)\) or under the root \(\sqrt{\cdot}\), where we will omit the \(|\cdot|\) characters. We will use python ([[https://docs.python.org/3/library/stdtypes.html#typesseq-common](https://docs.python.org/3/library/stdtypes.html#typesseq-common)]([https://docs.python.org/3/library/stdtypes.html#typesseq-common](https://docs.python.org/3/library/stdtypes.html#typesseq-common)), accessed on 18 June 2025) notation for individual characters and substrings. The string \(x\) consists of characters \(x[0],\ldots,x[|x|-1]\); the substring \(x[i:j]\) comprises the characters \(x[i],\ldots,x[j-1]\); if \(i\) is absent in this notation, we mean \(i=0\); if \(j\) is absent, we mean \(j=|x|\); if \(i\) or \(j\) is negative, we should add \(|x|\) to it. _Position_\(i\) in the string \(x\) refers to the boundary between characters \(x[i-1]\) and \(x[i]\) (position \(0\) is the left edge of the first character, and position \(|x|\) is the right edge of the last character). The notation \(x^{\texttt{n}}\) will represent the string that we get if we read the characters of the string \(x\) from right to left, so \(x^{\texttt{n}}[i]=x[|x|-1-i]\); prefixes and suffixes of the strings \(x\) and \(x^{\texttt{n}}\) are of course closely related: \(x^{\texttt{n}}[i:]=(x[:|x|-i])^{\texttt{n}}\) and \(x^{\texttt{n}}[:i]=(x[|x|-i:])^{\texttt{n}}\).  
We will frequently make use of prefix tables as we know them from the Knuth-Morris-Pratt algorithm [6]. For a given string \(x\), let \(\mathsf{P}_{x}[i]\) be largest integer \(j<i\) such that \(x[:]\) is a suffix of \(x[:]\) the table \(\mathsf{P}_{x}\) can be computed in \(O(x)\) time. For strings \(x\) and \(y\), we will further define \(\mathsf{P}_{yx}[i]\) as the largest integer \(j<|x|\) such that \(x[:]\) is a suffix of \(y[:]\); the table \(\mathsf{P}_{yx}\) can be computed in \(O(y)\) time by an algorithm very similar to that for \(\mathsf{P}_{x}\). In other words, \(\mathsf{P}_{x}\) and \(\mathsf{P}_{yx}\) tell us, for each prefix of \(x\) and of \(y\), what is the longest prefix of \(x\) that it ends with.  
The table \(\mathsf{P}_{yx}\) is useful, for example, in finding occurrences of the string \(x\) as a substring in the string \(y\): these occurrences end at those positions \(i\) (recall that position \(i\) is the boundary between characters \(y[i-1]\) and \(y[i]\)) where \(\mathsf{P}_{yx}[i-1]=|x|-1\) and \(y[i-1]=x[-1]\). This will also be useful to have stored in a table; so let \(\mathsf{O}_{yx}[i]=1\) if \(x\) appears in \(y\) starting at position \(i\) (that is, if \(y[i:i+|x|]=x\)), otherwise, let \(\mathsf{O}_{yx}[i]=0\). Let us further define a table of partial sums: \(\widetilde{\mathsf{O}}_{yx}[i]=\sum_{j=0}^{i}\mathsf{O}_{yx}[j]\), which therefore counts all occurrences of \(x\) as a substring in \(y\) at positions \(0\) to \(i\). All these tables can be calculated in linear time.  
Similar to the above precomputation of prefixes, we can also preprocess suffixes; let us define tables \(\mathsf{S}_{x}\) and \(\mathsf{S}_{yx}\) which tell us, for each suffix of \(x\) or \(y\), what is the longest suffix of \(x\) that it begins with. More precisely, let \(\mathsf{S}_{x}[i]\) be the smallest value \(j>i\) such that \(x[j\colon]\) is a prefix of \(x[i\colon]\); and let \(\mathsf{S}_{yx}[i]\) be the smallest value \(j>0\) such that \(x[j\colon]\) is a prefix of \(y[i\colon]\). Both tables can be computed in linear time by a similar procedure as for \(\mathsf{P}_{x}\) and \(\mathsf{P}_{yx}\), except that we process strings from right to left. (We can also reverse the strings and use the previous procedures for prefix tables; namely \(\mathsf{S}_{x}[i]=|x|-\mathsf{P}_{x^{n}}[|x|-i]\) and \(\mathsf{S}_{yx}[i]=|x|-\mathsf{P}_{y^{n}x^{n}}[|y|-i]\).)