# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 3 KMP-Based Permuted Pattern Matching Algorithms
### Multi-Track AC-Automaton  
In this subsection, we introduce a data structure called a multi-track AC-automaton that can perform dictionary matching on multi-tracks, namely _permuted dictionary matching_. Let \(D=\{\mathbb{P}_{1},\mathbb{P}_{2},\ldots,\mathbb{P}_{r}\}\) be a set of patterns of the same track count \(k\), called a _dictionary_, and let \(d=\sum_{i=1}^{r}m_{i}\) be the total length of the patterns in \(D\), where \(m_{i}=|\mathbb{P}_{i}|_{len}\). The multi-track AC-automaton of \(D\), denoted by \(\mathsf{MTAC}(D)\), consists of a set of states and three functions: _goto_, _failure_, and _output_ functions. Figure 1 shows an example of \(\mathsf{MTAC}(D)\). For a dictionary \(D\), the states of \(\mathsf{MTAC}(D)\) are \(\mathcal{S}=\{\mathsf{sort}(\mathbb{P}_{i})[:j]\mid\mathbb{P}_{i}\in D,0\leq j \leq m_{i}\}\). Each state corresponds to a prefix of \(\mathsf{sort}(\mathbb{P}_{i})\) for some \(\mathbb{P}_{i}\in D\). Unlike the original AC-automaton, the multi-track AC-automaton uses a multi-track symbol, instead of a single symbol, to define the goto function. The goto, failure, and output functions of \(\mathsf{MTAC}(D)\) are defined as follows. **Definition 4** (Goto function). : _We define the goto function \(\delta\) of \(\mathsf{MTAC}(D)\) by \(\delta(\mathsf{sort}(\mathbb{P}_{i})[:j]),\mathbb{C})=\mathsf{sort}(\mathbb{P}_ {i})[:j+1]\) iff \(\mathbb{C}=\mathsf{sort}(\mathbb{P}_{i})[j+1]\) for a state \(\mathsf{sort}(\mathbb{P}_{i})[:j]\) and a multi-track symbol \(\mathbb{C}\)._  
**Definition 5** (Failure function). : _The failure link of a state \(\mathsf{sort}(\mathbb{P}_{i})[:j]\) is defined as \(\mathsf{flink}(\mathsf{sort}(\mathbb{P}_{i})[:j])=\mathsf{sort}(\mathbb{P}_ {i}[l:j])\), where \(\mathbb{P}_{i}[l:j]\) is the longest proper suffix of \(\mathbb{P}_{i}[:j]\) such that \(\mathbb{P}_{i}[l:j]\) permuted-matches a prefix of some pattern in \(D\)._  
**Definition 6** (Output function). : _The output \(\mathsf{output}(\mathbb{P}_{i}[:j])\) of a state \(\mathsf{sort}(\mathbb{P}_{i})[:j]\) is the set of patterns that permuted-matches \(\mathbb{P}_{i}[l:j]\) for some \(1\leq l\leq j\)._  
Next, we explain how to construct \(\mathsf{MTAC}(D)\). We use _multi-track symbol tries_ to implement the goto function. **Definition 7** (Multi-track symbol trie). : _Let \(\mathcal{C}=\{\mathbb{C}_{1},...,\mathbb{C}_{\mathbb{\mathbb{\mathbb{\mathbb{ \mathbb{\mathbb{\mathbb{\mathbb{\mathbb{\mathbb{\mathbb{\mathbb{\mathbb{\mathbb{\mathbb{ \mathbb{    \mathbb{     }}}}}}}}}}}}\}\) be a set of multi-track symbols. The multi-track symbol trie of \(\  
**Lemma 6**: _Algorithm 3 constructs the goto function of the multi-track AC-automaton of a dictionary \(D=\{\mathbb{P}_{1},\mathbb{P}_{2},\ldots,\mathbb{P}_{r}\}\) in \(O(dk\log\sigma)\) time._  
The goto function \(\delta(s,\mathbb{C})\) is executed \(O(d)\) times, and \(\delta(s,\mathbb{C})\) can be computed in \(O(k\log\sigma)\) time. After constructing the goto function, we can construct the failure function of \(\mathsf{MTAC}(D)\). Algorithm 4 shows a construction algorithm for the failure function of a multi-track AC-automaton. In order to simplify the construction algorithm, we use a special state that reads any multi-track symbol to get to the root state.