# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 3 KMP-Based Permuted Pattern Matching Algorithms
### Multi-Track AC-Automaton
In addition, each state of the multi-track permuted matching automaton has a weight in order to determine whether flink should be executed or not. Figure 2 shows an example of a multi-track permuted matching automaton. Let \(\mathcal{S}\) be the set of states of \(\mathsf{MTPMA}(\mathbb{P})\). Each state of \(\mathsf{MTPMA}(\mathbb{P})\) corresponds to a prefix of \(P_{i}\), i.e., \(\mathcal{S}=\{P_{i}[:j]\mid 1\leq i\leq k,\ 0\leq j\leq m\}\). Each state \(s\) has a weight, which is the number of tracks containing \(s\) as a prefix. Moreover, a state \(s\) is called an _accept state_ if \(s=P_{i}\) for some \(i\). The goto and failure functions of \(\mathsf{MTPMA}(\mathbb{P})\) are defined as follows. **Definition 8** (Goto function). : _We define the goto function \(\delta\) as \(\delta(P_{i}[:j],c)=P_{i}[:j+1]\) iff \(c=P_{i}[j+1]\) for each state \(P_{i}[:j]\) and symbol \(c\)._

**Definition 9** (Failure function). : _Let \(S_{j}=\{P_{i}[:j]\mid 1\leq i\leq k\}\) be the set of states whose depth is \(j\). The failure link of the state is \(\mathsf{link}(P_{i}[:j])=P_{x}[:y]\in S_{y}\) such that \(P_{x}[:y]\) is a proper suffix of \(P_{i}[:j]\) and \(\mathbb{P}[:y]\) is the longest prefix of \(\mathbb{P}\) that permuted-matches with a proper suffix of \(\mathbb{P}[:j]\). The latter condition is similar to that of the multi-track KMP algorithm._

Next, we explain how to construct \(\mathsf{MTPMA}(\mathbb{P})\). Algorithm 7 constructs the goto function of a multi-track permuted matching automaton. We add a weight on each state each time we visit the state when reading each track. **Lemma 9**. : _Algorithm 7 constructs the goto function of \(\mathsf{MTPMA}(\mathbb{P})\) in \(O(mk\log\sigma)\) time._

Proof. : For each track, the number of executions of \(\delta(s,c)\) is \(m\), and there are \(k\) tracks in a pattern \(\mathbb{P}\). Moreover, \(\delta(s,c)\) can be executed in \(O(\log\sigma)\) time. After constructing the goto function, Algorithm 8 constructs the failure function of \(\mathsf{MTPMA}(\mathbb{P})\). For each state \(s\), we use a multi-track border array to determine the depth of \(\mathsf{link}(s)\). **Lemma 10**. : _Algorithm 8 constructs the failure function of \(\mathbb{P}\) in \(O(mk\log\sigma)\) time._

Proof. : Similarly to the proof of Theorem 7, the failure and goto functions are executed \(O(mk)\) times. Moreover, the execution time of the failure function is \(O(1)\), and that of the goto function is \(O(\log\sigma)\). From Lemmas 9 and 10 we get the following theorem. **Theorem 4**. : _The multi-track permuted matching automaton of a pattern \(\mathbb{P}\) can be constructed in \(O(mk\log\sigma)\) time._

Finally, by using \(\mathsf{MTPMA}(\mathbb{P})\), Algorithm 9 can perform permuted pattern matching on a multi-track text \(\mathbb{T}\). Algorithm 9 uses \(k\) pointers _activeStates_ to point to the current states. Note that all _activeStates_ always have the same depth. Algorithm 9 uses two conditions to determine whether it should execute the failure function or not. The first condition is when it cannot find the goto transition,

Figure 2: The multi-track permuted matching automaton \(\mathsf{MTPMA}(\mathbb{P})\) for \(\mathbb{P}=(\mathtt{aaabb},\mathtt{abaab},\mathtt{bbaaa})\). The asterisk is a special symbol that matches with any symbols in \(\Sigma\). and the second condition is when the number of state pointers in the state is more than the weight of the state. If any of the _activeStates_ fail, then all of the _activeStates_ execute the failure function, otherwise _activeStates_ executes the goto function. By using \(\mathsf{MTPMA}(\mathbb{P})\), Algorithm 9 performs permuted pattern matching on a multi-track string \(\mathbb{T}\) in \(O(nk\log\sigma)\) time. Proof. : Similarly to the proof of Theorem 3, the number of executions of the failure and goto function is \(O(nk)\). Since the execution time of the failure function is \(O(1)\) and the goto function is \(O(\log\sigma)\), Algorithm 9 runs in \(O(nk\log\sigma)\) time.