# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 4 Multi-Track Boyer-Moore and Horspool Algorithms
In the outer **while** loop starting at Line 7, the value of \(j\) is increased by at least one, so the loop is executed \(n-m+2\) times at most. In each execution of the outer loop, the inner **while** loop is executed \(m\) times at most, where multi-track symbols of the pattern and the text can be compared in \(O(k)\) time. \(\mathsf{BadSym}\) can be accessed in \(O(k\log\sigma)\) time, and \(\mathsf{GoodSuf}\) can be executed in \(O(1)\) time. Similarly to the original Horspool algorithm, the multi-track Horspool algorithm (MT-H) uses \(\mathsf{BadSym}\) to shift the pattern. **Theorem 7**. : _Given a multi-track text \(\mathbb{T}\) and a pattern \(\mathbb{P}\), MT-H outputs all occurrence positions of \(\mathbb{P}\) in \(\mathbb{T}\) in \(O(nk(m+\log\sigma)+n(k+\sigma))\) time with \(O(m(k\log\sigma+\sigma))\) preprocessing time._  
Proof. : Similar to the proof of Theorem 6. _Boyer-Moore and Horspool Matching Algorithms with Track Trie_  
The two algorithms presented in the previous subsections determine if two multi-tracks permuted-match by sorting them. In this subsection, we present another idea for this task using a data structure called a _track trie_. The track trie \(\mathsf{TrackTrie}(\mathbb{P})\) of a multi-track \(\mathbb{P}\) stores all the reversed strings of the tracks of \(\mathbb{P}\), that is \(\{P_{1}^{R},P_{2}^{R},\ldots,P_{k}^{R}\}\). Figure 3a shows the track trie of a multi-track pattern \(\mathbb{P}=(\texttt{bbaba},\texttt{abbba},\texttt{aaabb})\). Algorithm 12 is the construction algorithm of \(\texttt{TrackTrie}(\mathbb{P})\). For a node \(s\) of \(\texttt{TrackTrie}(\mathbb{P})\) and a symbol \(c\in\Sigma\), the goto function \(\delta(s,c)\) returns the child of \(s\) that has an edge labeled \(c\). We naturally extend it to the domain \(\Sigma^{*}\) by \(\delta(s,\varepsilon)=s\) and \(\delta(s,aw)=\delta(\delta(s,a),w)\) for any \(a\in\Sigma\) and \(w\in\Sigma^{*}\). We also associate a weight with each node to find mismatch on a text, as we explain later. ```
1 Function\(\texttt{constructTrackTrie}(\mathbb{P})\)
2 newNode\(\leftarrow\) root;
3 weight(root)\(\gets k\);
4 for\(i\gets 1\)to\(k\)do
5 activeNode\(\leftarrow\) root;
6 for\(j\gets m\)to\(1\)do
7 if\(\delta(activeNode,\mathbb{P}[j][i])=\texttt{NULL}\)then
8 newNode\(\leftarrow\) newNode\(+\) 1;
9 weight(newNode)\(\leftarrow\) 1;
10\(\delta(activeNode,\mathbb{P}[j][i])\)\(\leftarrow\) newNode;
11\(activeNode\leftarrow\) newNode;
12
13 else
14\(activeNode\leftarrow\delta(activeNode,\mathbb{P}[j][i])\);
15 weight(activeNode)\(\leftarrow\) weight(activeNode)\(+\) 1;
16
17
```  
**Algorithm 12**Track trie construction algorithm. Theorem 8: Algorithm 12 constructs \(\texttt{TrackTrie}(\mathbb{P})\) in \(O(mk\log\sigma)\) time. Proof: The function _goto_ can be calculated in \(O(\log\sigma)\) time by binary search. On each execution of the inner **for** loop (Line 6), Algorithm 12 executes _goto_ to check the child nodes of _activeNode_. If there is no node with an edge labeled \(\mathbb{P}[j][i]\), then a new node is constructed, which can be done in \(O(1)\) time. On the other hand, if there is a node with an edge labeled \(\mathbb{P}[j][i]\), Algorithm 12 accesses the child node and then increases its weight by one. The total number of iterations of the inner loop is _mk_. For a given multi-track text \(\mathbb{T}\) and a position \(i\), Algorithm 13 finds a mismatch position in two cases: (1) when a track cannot find its _goto_ destination, and (2) when the number of tracks that have the same string \(w\) is more than the weight of the node that represents the string \(\delta(root,w)\). Those mismatch conditions are illustrated in Figure 3b,c, respectively. Figure 3b shows that the track trie cannot find a transition for the second symbol b of the third track. On the other hand, Figure 3c shows that \(\mathbb{T}_{2}[3:]\) has two \"bba\" on its track; however, the \(\mathbb{P}[3:]\) has only one \"bba\" on its track, i.e., the node that represents \"bba\" has one on its weight.