# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 3 KMP-Based Permuted Pattern Matching Algorithms
### Multi-Track AC-Automaton
```
1 Function\(\mathsf{constructFailureFunction}(D)\)
2 compute \(SI[i][j]\leftarrow\mathsf{SI}(\mathbb{P}_{i}[j:])\) for \(1\leq i\leq r\) and \(1\leq j\leq m_{i}\);
3\(\mathsf{flink}(\mathit{root})\leftarrow\bot\);
4 push root to queue;
5 whilequeue \(\
eq\varnothing\)do
6 pop v from queue;
7 for\(\mathbb{C}\) such that \(\delta(v,\mathbb{C})=u\
eq\mathsf{NULL}\)do
8 push \(u\) to queue;
9\(s\leftarrow\mathsf{flink}(v)\);
10\(i\leftarrow\mathsf{label}(u)\);
11 while\(\delta(s,\mathbb{P}_{i}[\mathsf{depth}(u)]\langle SI[i][\mathsf{depth}(u)- \mathsf{depth}(s)]\rangle)=\mathsf{NULL}\)do
12\(s\leftarrow\mathsf{flink}(s)\);
13\(\mathsf{flink}(u)\leftarrow\delta(s,\mathbb{P}_{i}[\mathsf{depth}(u)]\langle SI [i][\mathsf{depth}(u)-\mathsf{depth}(s)]\rangle)\);
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
310
32
334
35
36
37
38
390
391
392
393
401
411
422
432
445
456
467
471
482
493
504
5105
5206
5394
607
5495
6108
6209
6300
6401
6502
6510
6603
6711
682
6912
6921
6


```
1 FunctionconstructOutputFunction(\(D\))
2 compute \(SI[i][j]\leftarrow SI[\mathbb{P}_{i}[i\,:]]\) for \(1\leq i\leq r\) and \(1\leq j\leq m_{i}\);
3 for\(i\gets 1\)to\(r\)do
4\(v\gets root\);
5 for\(1\leq j\leq m_{i}\)do
6\(v\leftarrow\delta(v,\mathbb{P}_{i}[j]\langle SI[i][1]\rangle)\);
7 if\(j=m_{i}\)then
8\(\texttt{output}(v)\leftarrow\texttt{output}(v)\cup\{i\}\);
9 push _root_ to _queue_;
10 whilequeue\(\
eq\emptyset\)do
11 pop\(v\) from queue;
12\(\texttt{output}(v)\leftarrow\texttt{output}(v)\cup\texttt{output}(\texttt{ flink}(v))\);
13 for\(\mathbb{C}\) such that \(\delta(\texttt{activeState},\mathbb{C})=s\
eq\texttt{NULL}\)do
14 push \(s\) to queue;
```
**Algorithm 5**Multi-track AC-automaton output function construction algorithm. By using the multi-track AC-automaton of \(D\), we can perform permuted dictionary matching on a text \(\mathbb{T}\), as shown in Algorithm 6. Let \(v\) be the current state of the multi-track AC-automaton. For each position \(i\) on \(\mathbb{T}\), Algorithm 6 uses the sorted index of \(\mathbb{T}[i-\texttt{depth}(v):]\) to determine the permutation of \(\mathbb{T}[i]\) that is used in the goto function. ```
1 Function\(\texttt{MTACADictionaryMatching}(\mathbb{T})\)
2 compute \(SI[i]\leftarrow SI[\mathbb{T}[i\,:]]\) for \(1\leq i\leq n\);
3\(v\gets root\);
4 for\(1\leq i\leq n\)do
5 while\(\delta(v,\mathbb{T}[i]\langle SI[i-\texttt{depth}(v)+1]\rangle)=\texttt{NULL}\)do\(v\leftarrow\texttt{flink}(v)\);
6\(v\leftarrow\delta(v,\mathbb{T}[i]\langle SI[i-\texttt{depth}(v)+1]\rangle)\);
7 for\(k\in\texttt{output}(v)\)do\(\texttt{output}(k,i-m_{k}+1)\);
```
**Algorithm 6**Permuted dictionary matching algorithm by using multi-track AC-automaton. **Theorem 3**: _Permuted dictionary matching on a multi-track text \(\mathbb{T}\) can be performed in \(O(nk\log\sigma)\) time by using the multi-track AC-automaton of \(D\)._

The running time of Algorithm 6 can be evaluated by counting the number of executions of \(\delta(s,\mathbb{C})\). First, for each \(i\), \(\delta(s,\mathbb{C})\) is executed at least once on the \(v\) transition. Next, \(\delta(s,\mathbb{C})\) is executed to check whether the transition is NULL or not. In this case, the number of executions of \(\delta(s,\mathbb{C})\) is the same as that of flink. The latter is, at most, \(n\), because whenever \(\delta(s,\mathbb{C})\) is executed, the depth of \(v\) is increased by one, and whenever flink is executed, the depth of \(v\) is decreased by at least one. Therefore, the number of executions of \(\delta(s,\mathbb{C})\) is \(O(n)\). ### Multi-Track Permuted Matching Automaton

In this subsection, we describe a data structure called a multi-track permuted matching automaton that can perform permuted pattern matching on a multi-track text \(\mathbb{T}\) online, by preprocessing a multi-track pattern \(\mathbb{P}\). For a multi-track pattern \(\mathbb{P}=(P_{1},P_{2},...,P_{k})\), the multi-track permuted matching automaton of \(\mathbb{P}\), denoted by \(\texttt{MTPMA}(\mathbb{P})\), consists of a set of states and two functions, goto and failure functions.