# Permuted Pattern Matching Algorithms on Multi-Track Strings
## 3 KMP-Based Permuted Pattern Matching Algorithms
### Multi-Track KMP Algorithm  
Similar to the original KMP algorithms, the _multi-track KMP algorithm_ uses _multi-track border arrays_ to compute the shift amount when the algorithm finds a mismatch. First, we define borders for multi track strings. **Definition 2** (Borders of multi-tracks). : _A border of a multi-track \(\mathbb{P}\) is any multi-track that permuted-matches with a prefix and a suffix of \(\mathbb{P}\). Moreover, a border \(\mathbb{B}\) of \(\mathbb{P}\) is called proper if \(\mathbb{B}\bowtie\mathbb{P}\)._  
We can easily confirm the following lemma. **Lemma 4**. : _For any two borders \(\mathbb{B}_{1}\) and \(\mathbb{B}_{2}\) of \(\mathbb{P}\), if \(|\mathbb{B}_{1}|_{len}<|\mathbb{B}_{2}|_{len}\), then \(\mathbb{B}_{1}\) is a border of \(\mathbb{B}_{2}\)._  
Let \(\mathbb{T}[i:i+j]\bowtie\mathbb{P}[1:j+1]\) for some \(i\) and \(j\). If \(\mathbb{T}[i+x:i+x+m-1]\bowtie\mathbb{P}[1:m]\) for some \(x\leq j\), then \(\mathbb{T}[i:i+(j-x)]\bowtie\mathbb{P}[1:(j-x)+1]\) and \(\mathbb{T}[i+x:i+j]\bowtie\mathbb{P}[1:(j-x)+1]\) hold, i.e., \(\mathbb{P}[1:(j-x)+1]\) is a proper border of \(\mathbb{P}[1:j+1]\). Therefore, if \(\mathbb{T}[i:i+j]\bowtie\mathbb{P}[1:j+1]\) and \(\mathbb{T}[i:i+j]\bowtie\mathbb{P}[1:j+1]\), we can safely shift \(\mathbb{P}\) by \(x\), where \((j-x+1)\) is the length of the longest proper border of \(\mathbb{P}[1:j+1]\). We store the length of the longest proper border of \(\mathbb{P}[1:j+1]\) for \(1\leq j\leq m\) as the border array of \(\mathbb{P}\). **Definition 3** (Multi-track border array). : _Given a multi-track \(\mathbb{P}\) of \(|\mathbb{P}|_{len}=m\), the border array \(\text{\emph{Border}}_{\mathbb{P}}\) of \(\mathbb{P}\) is an array of length \(m+1\), where the \(i^{th}\) element of \(\text{\emph{Border}}_{\mathbb{P}}\) is the length of the longest proper border of \(\mathbb{P}[1:i]\). Formally,_  
\[\text{\emph{Border}}_{\mathbb{P}}[i]=\max\left\{j\mid\mathbb{P}[1:j]\bowtie \mathbb{P}[i-j+1:i],0\leq j<i\right\}. \tag{1}\]  
For algorithmic purpose, we define \(\text{\emph{Border}}_{\mathbb{P}}[0]=-1\). Algorithm 1 constructs the multi-track border array of an input \(\mathbb{P}\). **Lemma 5**. : _Given a multi-track \(\mathbb{P}\) of \(|\mathbb{P}|_{len}=m\) and \(|\mathbb{P}|_{num}=k\), Algorithm 1 constructs the border array of \(\mathbb{P}\) in \(O(mk)\) time._  
Proof. : First, we show the correctness of the algorithm by induction. Assume we have computed the longest proper border of \(\mathbb{P}[:j]\) and stored it in \(\text{\emph{Border}}[j]\) for \(1\leq j\leq i\). Let \(\mathbb{P}[:b]\) be the longest proper border of \(\mathbb{P}[:i+1]\). Clearly, \(\mathbb{P}[:b-1]\) is a border of \(\mathbb{P}[:i]\). Using Lemma 4, we can find \(b-1\) by finding \(\max\{j\mid\mathbb{P}[:j]\) is a proper border of \(\mathbb{P}[:i]\) and \(\mathbb{P}[:j+1]\bowtie\mathbb{P}[i-j+1:i+1]\}\). Since \(\text{\emph{Border}}[j]\) is the longest proper border of \(\mathbb{P}[:j]\), the algorithm can find \(b-1\) by updating \(j\gets\text{\emph{Border}}[j]\) from \(j=i\) until \(\mathbb{P}[:\text{\emph{Border}}[j]+1]\bowtie\mathbb{P}[i-\text{\emph{Border}} [j]+1:i+1]\) holds. Therefore, Algorithm 1 computes the border array of \(\mathbb{P}\) correctly. Next, we show the computation time of the algorithm. Using Lemma 1, \(SI\) can be computed in \(O(mk)\). Both **while** loops are called \(O(m)\) times at most, since \(i-j\leq i\leq m+1\), and the value of \(i\) always increases each time the outer loop is called, while the value of \(i-j\) always increases each time the inner loop is called. Each comparison of \(\mathbb{P}[j]\langle\mathsf{SI}(\mathbb{P}[1:])\rangle\) and \(\mathbb{P}[i]\langle\mathsf{SI}(\mathbb{P}[i-j:])\rangle\) consumes \(O(k)\) time; hence, Algorithm 1 runs in \(O(mk)\) time. Algorithm 2 shows the pseudocode of the MTKMPalgorithm. The MTKMP algorithm performs permuted pattern matching from left to right of the pattern and the text.