# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 4 Multi-Track Boyer-Moore and Horspool Algorithms
```
1 FunctionComputeSuf\((\mathbb{P})\)
2 compute \(RI[i]\leftarrow\mathsf{RI}(\mathbb{P}[:i])\) for \(1\leq i\leq m\);
3\(\mathsf{suf}[m]\gets m\), \(j\gets m\), \(l\gets m\);
4 for\(i\gets m-1\)to\(1\)do
5 if\(i>l\)and\(\mathsf{suf}[m-(j-i)]<i-l\)then
6\(\mathsf{suf}[i]\leftarrow\mathsf{suf}[m-(j-i)]\);
7
8 else
9 if\(i<l\)then\(l\gets i\);
10\(j\gets l\);
11 while\(l>0\)and\(\mathbb{P}[l]\langle RI[j]\rangle=\mathbb{P}[l+m-j]\langle RI[m]\rangle\)do
12\(k\gets l-1\);
13\(\mathsf{suf}[i]\gets j-l\);
14
15
16 return suf;
17
18 FunctionComputeGoodSuf\((\mathbb{P})\)
19\(\mathsf{suf}\leftarrow\)ComputeSuf\((\mathbb{P})\);
20\(j\gets 1\);
21 for\(i\gets 1\)to\(m\)do\(\mathsf{GoodSuf}[i]\gets m\);
22 for\(i\gets m\)to\(1\)do
23 if\(\mathsf{suf}[i]=i\)then
24 while\(j\leq m-i\)do
25 if\(\mathsf{GoodSuf}[j]=m\)then\(\mathsf{GoodSuf}[j]\gets m-i\);
26\(j\gets j+1\);
27
28
29 for\(i\gets 1\)to\(m-1\)do\(\mathsf{GoodSuf}[m-\mathsf{suf}[i]]\gets m-i\);
30
31 return GoodSuf;
32
33
34
35 FunctionComputeBadSym\((\mathbb{P})\)
36 compute \(RI[i]\leftarrow\mathsf{RI}(\mathbb{P}[:i])\) for \(1\leq i\leq m\);
37 for\(i\gets 1\)to\(m-1\)do
38 if\(\mathsf{BadSym}(\mathbb{P}[i]\langle RI[i]\rangle)=m\)then
39\(\mathsf{BadSym}.add(\mathbb{P}[i]\langle RI[i]\rangle,m-i)\);
40
41 else
42\(\mathsf{BadSym}(\mathbb{P}[i]\langle RI[i]\rangle)\gets m-i\);
43
44 return BadSym;
```  
**Algorithm 10**MT-BM and MT-H preprocessing functions. **Lemma 11**. : _The function ComputeSuf computes the array suf in \(O(m(k+\sigma))\) time._  
Proof. : First, \(RI\) can be computed in \(O(m(k+\sigma))\) time by using radix sort. The **for** loop is executed \(m-1\) times, and the **while** loop in Line 11 is executed \(m\) times at most through the whole run, because \(k\) is always reduced in each loop. A comparison of two multi-track symbols of the pattern that was executed in each loop can be computed in \(O(k)\) time. **Lemma 12**. : _The function ComputeGoodSuf computes \(\mathsf{GoodSuf}\) in \(O(m)\) time._Proof. : All the **for** loops are executed \(m\) times at most. The **while** loop is executed \(m\) times at most through the whole execution of the algorithm, since \(j\) is always increased and does not exceed \(m\). **Lemma 13**. : _The function \(\mathsf{ComputeBadSym}\) computes \(\mathsf{BadSym}\) in \(O(m(k\log\sigma+\sigma))\) time._  
Proof. : \(RI\) can be computed in \(O(m(k+\sigma))\) time by using radix sort. Each edge in the trie of \(\mathsf{BadSym}\) can be accessed in \(O(\log\sigma)\) time by using a binary search. Since the depth of the trie is, at most, \(k\), each \(\mathsf{BadSym}(\mathbb{P}[i])\) for \(1\leq i\leq m\) can be added and accessed in \(O(k\log\sigma)\) time. By using both \(\mathsf{GoodSuf}_{\mathbb{P}}\) and \(\mathsf{BadSym}_{\mathbb{P}}\), MT-BM outputs the positions of the text that are permuted-matched with the pattern. The matching algorithm of MT-BM is shown in Algorithm 11. ```
1 Function\(\mathsf{MTBM}(\mathbb{T},\mathbb{P})\)
2 compute \(R[i]\leftarrow\mathsf{R}(\mathbb{T}[:i])\) for \(1\leq i\leq n\);
3 compute \(\mathbb{P}_{sort}\leftarrow\mathsf{R}(\mathbb{P})\);
4 BadSym\(\leftarrow\) ComputeBadSym\((\mathbb{P})\);
5 GoodSuf\(\leftarrow\) ComputeGoodSuf\((\mathbb{P})\);
6\(j\gets 0\);
7 while\(j\leq n-m+1\)do
8\(i\gets m\);
9 while\(i>0\)and\(\mathbb{T}[i+j]\langle R[j+m]\rangle=\mathbb{P}_{sort}[i]\)do
10\(i\gets i-1\);
11 if\(i\leq 0\)then
12 output\(j+1\);
13\(j\gets j+\mathsf{GoodSuf}[0]\);
14
15 else
16\(j\gets j+\max(\mathsf{GoodSuf}[i],\mathsf{BadSym}(\mathbb{T}[i+j]\langle R [i+j]\rangle)-(m-i))\);
17
18
```  
**Algorithm 11**Multi-track Boyer-Moore algorithm. **Theorem 6**. : _Given a multi-track text \(\mathbb{T}\) and a pattern \(\mathbb{P}\), MT-BM 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. : From Lemmas 11-13, Algorithm 11 needs \(O(m(k\log\sigma+\sigma))\) time for preprocessing. Next, \(RI\) can be computed in \(O(n(k+\sigma))\) time by using radix sort.