# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 2 Notation and Definition on Multi-Track Strings
reverse_ of a multi-track is \(\mathbb{W}=(W_{1},\ldots,W_{k})\) is \(\mathbb{W}^{R}=(W_{1}^{R},\ldots,W_{k}^{R})\). The sorted index of the reverse multi-track, denoted by \(\mathsf{RI}(\mathbb{W})\), is a permutation \((r_{1},\ldots,r_{k})\) such that \(w_{r_{i}}^{R}\preceq w_{r_{i+1}}^{R}\) for any \(1\leq i<k\). **Lemma 1** ([7]). : _Let \(SI_{W}\) be a two-dimensional array such that \(SI_{W}[i]=\mathsf{SI}(\mathbb{W}[i:])\) for \(1\leq i\leq n\). \(SI_{W}\) can be computed in \(O(nk)\) time offline, where \(n=|\mathbb{P}|_{len}\) and \(k=|\mathbb{P}|_{num}\)._  
**Lemma 2**. : _Let \(RI_{W}\) be a two-dimensional array such that \(RI_{W}[i]=\mathsf{RI}(\mathbb{W}[i:])\) for \(1\leq i\leq n\). \(RI_{W}\) can be computed in \(O(n(k+\sigma))\) time online, where \(n=|\mathbb{P}|_{len}\) and \(k=|\mathbb{P}|_{num}\)._  
Proof. : Clearly, \(RI_{W}\) can be computed in \(O(n(k+\sigma))\) by using a radix sort algorithm. For two multi-tracks \(\mathbb{X}=(X_{1},X_{2},\ldots,X_{k})\) and \(\mathbb{Y}=(Y_{1},Y_{2},\ldots,Y_{k})\) of the same length, we say that \(\mathbb{X}\)_permuted-matches_\(\mathbb{Y}\) if \(\mathbb{X}=\mathbb{Y}\langle\mathbf{r}\rangle\) for some permutation \(\mathbf{r}\), and it is denoted by \(\mathbb{X}\bowtie\mathbb{Y}\). **Lemma 3** ([7]). : _For two multi-tracks \(\mathbb{X}\) and \(\mathbb{Y}\), \(\mathbb{X}\bowtie\mathbb{Y}\) if and only if \(\mathsf{sort}(\mathbb{X})=\mathsf{sort}(\mathbb{Y})\)._  
Throughout this paper, we assume that \(\mathbb{P}\) is a pattern with \(|\mathbb{P}|_{num}=k\) and \(|\mathbb{P}|_{len}=m\), and \(\mathbb{T}\) is text with \(|\mathbb{T}|_{num}=k\) and \(|\mathbb{T}|_{len}=n\geq m\). The pattern matching problem on multi-tracks is defined as follows. **Definition 1** (Permuted pattern matching [7]). : _Given a multi-track text \(\mathbb{T}\) and a multi-track pattern \(\mathbb{P}\), compute all positions \(\mathsf{i}\) that satisfy \(\mathbb{P}\bowtie\mathbb{T}[i:i+m-1]\). We call such positions occurrence positions of \(\mathbb{P}\) in \(\mathbb{T}\)._  
For example, given a text \(\mathbb{T}=\left( \begin{array}{c}\texttt{aabaaaaaa},\\ \texttt{abaabbaa},\\ \texttt{baaaababa}\end{array} \right)\) and a pattern \(\mathbb{P}=\left( \begin{array}{c}\texttt{aba},\\ \texttt{baa},\\ \texttt{aaaa}\end{array} \right)\), we can see that the pattern \(\mathbb{P}\) matches \(\mathbb{T}\) at two because \(\mathbb{T}[2:4]=\mathbb{P}\). Moreover, the pattern \(\mathbb{P}\) permuted-matches \(\mathbb{T}\) at six, since \(\mathbb{P}\langle 3,2,1\rangle=\left( \begin{array}{c}\texttt{aaa},\\ \texttt{baa},\\ \texttt{aba}\end{array} \right)=\mathbb{T}[6:8]\). Therefore, we should output two and six in this case. We remark that [PERSON] et al. [7] defined a more general problem called the _sub-permuted pattern matching_, where we have \(|\mathbb{T}|_{num}\geq|\mathbb{P}|_{num}\), and our task is to find a partial permutation \((r_{1},\ldots,r_{|\mathbb{P}|_{num}})\) of \((1,\ldots,|\mathbb{T}|_{num})\) and a position \(i\) for which \(\mathbb{P}\bowtie\mathbb{T}\langle r_{1},\ldots,r_{|\mathbb{P}|_{num}}\rangle[i: i+m-1]\) holds. However, in this paper, we only consider the case \(|\mathbb{T}|_{num}=|\mathbb{P}|_{num}\), which was called _full-permuted pattern matching_ in [7].