# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 2 Notation and Definition on Multi-Track Strings  
Let \(\Sigma\) be a _totally-ordered alphabet_ and \(\sigma=|\Sigma|\) be the size of the alphabet. An element of \(\Sigma^{*}\) is called a _string_. For a string \(W\in\Sigma^{*}\), the length of \(W\) is denoted by \(|W|\). The _empty string_, denoted by \(\varepsilon\), is a string of length zero. For a string \(W\in\Sigma^{*}\) of length \(n\), \(W[i]\) denotes the \(i^{\text{th}}\) symbol of \(W\), and \(W[i:j]=W[i]W[i+1]\ldots W[j]\) denotes a substring of \(W\) that begins at \(i\) and ends at \(j\) for \(1\leq i\leq j\leq n\). For convenience, we abbreviate \(W[1:i]\) to \(W[:i]\) and \(W[i:n]\) to \(W[i:]\); these terms are known as the _prefix_ and the _suffix_ of \(W\), respectively. Moreover, let \(W[i:j]=\varepsilon\) if \(i>j\). The reverse string of \(W\) is denoted by \(W^{R}=W[n]W[n-1]\ldots W[2]W[1]\). For two strings, \(X\) and \(Y\), \(X\prec Y\) denotes that \(X\) is lexicographically smaller than \(Y\), and \(X\preceq Y\) denotes that either \(X=Y\) or \(X\prec Y\). A _multi-track symbol_\(\mathbb{C}=(c_{1},c_{2},\ldots,c_{k})\) is a \(k\)-tuple of symbols \(c_{i}\in\Sigma\). A _multi-track string_ (or _multi-track_ for short) \(\mathbb{W}=(W_{1},W_{2},\ldots,W_{k})\) is a \(k\)-tuple of strings \(W_{i}\in\Sigma^{*}\) where \(|W_{1}|=|W_{2}|=\cdots=|W_{k}|\), and each \(W_{i}\) is called the \(i^{\text{th}}\)_track_ of \(\mathbb{W}\). The length \(n\) of strings in \(\mathbb{W}\) is called the _length_ of \(\mathbb{W}\) and denoted by \(|\mathbb{W}|_{\text{tem}}\), and the number \(k\) of tracks in \(\mathbb{W}\) is called the _track count_ of \(\mathbb{W}\) and is denoted by \(|\mathbb{W}|_{\text{mem}}\). For a multi-track symbol \(\mathbb{C}=(c_{1},c_{2},\ldots,c_{k})\), we define \(\mathbb{C}[i]=c_{i}\). For a multi-track \(\mathbb{W}\) of track count \(k=|\mathbb{W}|_{\text{mem}}\), \(\mathbb{W}[i]=(W_{1}[i],W_{2}[i],\ldots,W_{k}[i])\) denotes the \(i^{\text{th}}\) multi-track symbol, and \(\mathbb{W}[i][j]\) denotes \(W_{j}[i]\) for \(1\leq i\leq|\mathbb{W}|_{\text{tem}}\) and \(1\leq j\leq|\mathbb{W}|_{\text{mem}}\). Moreover, \(\mathbb{W}[i:j]=(W_{1}[i:j],W_{2}[i:j],\ldots,W_{k}[i:j])\) denotes a substring of \(\mathbb{W}\) that begins at \(i\) and ends at \(j\) for \(1\leq i\leq j\leq|\mathbb{W}|_{\text{tem}}\). Similarly to the notation for strings, \(\mathbb{W}[:i]\) and \(\mathbb{W}[i:]\) mean \(\mathbb{W}[1:i]\) and \(\mathbb{W}[i:|\mathbb{W}|_{\text{tem}}]\), which are called the _prefix_ and the _suffix_ of \(\mathbb{W}\), respectively. Let \(\mathbf{r}=(r_{1},r_{2},\ldots,r_{k})\) be a permutation of \((1,2,\ldots,k)\). For a multi-track \(\mathbb{W}=(W_{1},W_{2},\ldots,W_{k})\), \(\mathbb{W}\langle\mathbf{r}\rangle=\mathbb{W}\langle r_{1},r_{2},\ldots,r_{k} \rangle=(W_{r_{1}},\ldots,W_{r_{k}})\) is called a _permuted multi-track_ of \(\mathbb{W}\). The _sorted index_\(\mathsf{SI}(\mathbb{W})\) of a multi-track \(\mathbb{W}\) is a permutation \((r_{1},\ldots,r_{k})\) such that \(W_{r_{i}}\preceq W_{r_{i+1}}\) for any \(1\leq i<k\), where we assume \(r_{i}<r_{i+1}\) in the case \(W_{r_{i}}=W_{r_{i+1}}\). The _sorted multi-track_\(\mathsf{sort}(\mathbb{W})\) is defined as \(\mathbb{W}\langle\mathsf{SI}(\mathbb{W})\rangle\). The \begin{table}
\begin{tabular}{l c c} \hline \hline
**Algorithm** & **Preprocessing Time** & **Matching Time** \\ \hline AC-automaton-based [7] & \(O(mk\log\sigma)\) & \(O(nk\log\sigma)\) \\ Multi-track KMP & \(O(mk)\) & \(O(nk)\) \\ MTAC-automaton & \(O(dk\log\sigma)\) & \(O(nk\log\sigma)\) \\ MT permuted matching automaton & \(O(mk\log\sigma)\) & \(O(nk\log\sigma)\) \\ MT Boyer–Moore & \(O(m(k\log\sigma+\sigma))\) & \(O(nk(m+\log\sigma)+n(k+\sigma))\) \\ MT Horspool & \(O(m(k\log\sigma+\sigma))\) & \(O(nk(m+\log\sigma)+n(k+\sigma))\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of the algorithms for permuted pattern matching. Multi-track AC-automaton can find occurrences of _multiple_ patterns.