# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 5 Filtering Algorithm on a Multi-Track String  
In this section, we propose filtering algorithms for permuted pattern matching. The filtering algorithm uses a function to transform a multi-track string into another sequence. Then, the algorithm implements a pattern matching algorithm on the transformed pattern and text to get candidate positions where the pattern may permuted-match. Finally, every candidate position is checked for whether the pattern is permuted-matched in each position or not. The filtering algorithm uses a function \(\phi\) that inputs a multi-track \(\mathbb{W}\) and outputs a sequence of length \(|\mathbb{W}|_{len}\). The function \(\phi\) must have a _false-positive_ property, that is, for two multi-tracks \(\mathbb{X}\) and \(\mathbb{Y}\), if \(\mathbb{X}\bowtie\mathbb{Y}\), then \(\phi(\mathbb{X})=\phi(\mathbb{Y})\). We can use any hash function such as the Karp-Rabin fingerprint [14] and locality-sensitive hashing [15]. We describe the filtering algorithm by using a simple function \(\beta\) that is defined as follows. Definition 13 (Bucket function \(\beta\)): _For \(\mathbb{W}=(W_{1},W_{2},\ldots,W_{k})\), \(\beta(\mathbb{W})=(B_{1},B_{2},\ldots,B_{\sigma})\) such that \(B_{j}[i]\) is the number of the \(i^{th}\) symbol in \(\mathbb{Z}[i]\)._  
For example, for a multi-track \(\mathbb{W}=(\texttt{abab},\texttt{bac},\texttt{aabb},\texttt{cabb},\texttt{ abba})\), \(\beta(\mathbb{W})\) is as follows,\[\left( \begin{array}{cccc}\mathbf{a}&\mathbf{b}&\mathbf{a}&\mathbf{b}\\ \mathbf{b}&\mathbf{b}&\mathbf{a}&\mathbf{c}\\ \mathbf{a}&\mathbf{a}&\mathbf{b}&\mathbf{b}\\ \mathbf{c}&\mathbf{a}&\mathbf{b}&\mathbf{b}\\ \mathbf{a}&\mathbf{b}&\mathbf{b}&\mathbf{a}\end{array} \right),\ \ \beta(\mathbb{Z})=\left( \begin{array}{cccc}3&2&2&1\\ 1&3&3&3\\ 1&0&0&1\end{array} \right). \tag{2}\]  
\(\beta(\mathbb{W})\) can be computed in \(O(n(k+\sigma))\) time by counting all symbols in \(\mathbb{W}\). Algorithm 14 shows an example of filtering algorithm for permuted pattern matching. This algorithm uses \(\beta\) as a hash function, and the KMP algorithm as a patten matching algorithm. First, the algorithm computes \(\mathbb{P}^{\prime}=\beta(\mathbb{P})\) and \(\mathbb{T}^{\prime}=\beta(\mathbb{T})\) and then constructs the border array \(\mathit{Border}_{\mathbb{P}^{\prime}}\) using the same procedure as the KMP algorithm. Next, the algorithm performs pattern matching on \(\mathbb{P}^{\prime}\) and \(\mathbb{T}^{\prime}\). When a mismatch occurs, the pattern is shifted by using \(\mathit{Border}_{\mathbb{P}^{\prime}}\). If \(\mathbb{P}^{\prime}\) matches \(\mathbb{T}^{\prime}[i:j]\), then the algorithm checks whether the pattern \(\mathbb{P}\) permuted-matches \(\mathbb{T}[i:j]\) or not, and it outputs the position if true. ```
1 Function\(\mathsf{multiTrackFiltering}(\mathbb{P})\)
2\(\mathbb{T}^{\prime}\leftarrow\beta(\mathbb{T});\mathbb{P}^{\prime}\leftarrow \beta(\mathbb{P});\)
3 constructBorderArray(\(\mathbb{P}^{\prime}\));
4\(i\gets 1;j\gets 1;\)
5 while\(i\leq n\)do
6 while\(j>0\) and \(\mathbb{T}^{\prime}[i]\
eq\mathbb{P}^{\prime}[j]\)do\(j\leftarrow\mathit{Border}[j]\);
7\(i\gets i+1;j\gets j+1;\)
8 if\(j>m\)then
9 if\(\mathbb{T}[i-j+1:i-1]\bowtie\mathbb{P}\)then output\((i-j+1)\);
10\(j\leftarrow\mathit{Border}[j]\);
11 Function\(\mathsf{constructBorderArray}(\mathbb{P}^{\prime})\)
12\(i\gets 1;j\gets 1;\)
13\(\mathit{Border}[1]\gets 0\);
14 while\(i\leq m\)do
15 while\(j>0\) and \(\mathbb{P}^{\prime}[i]\
eq\mathbb{P}^{\prime}[j]\)do\(j\leftarrow\mathit{Border}[j]\);
16\(i\gets i+1;j\gets j+1;\)
17 if\(i\leq m\) and \(\mathbb{P}^{\prime}[i]=\mathbb{P}^{\prime}[j]\)then\(\mathit{Border}[j]\gets\mathit{Border}[i]\);
18 else\(\mathit{Border}[j]\gets i\);
```  
**Algorithm 14**Filtering algorithm for permuted pattern matching.