A Simple Reduction for Full-Permuted Pattern Matching Problems on Multi-Track Strings.

In this paper we study a variant of string pattern matching which deals with tuples of strings known as \textit{multi-track strings}. Multi-track strings are a generalisation of strings (or \textit{single-track strings}) that have primarily found uses in problems related to searching multiple genomes and music information retrieval \cite{Lemstrom:2003:MPS:1756553.1756571,Lemstrom:2003:TIP:967792.967793}. There is a \textit{full-permuted-match} between two multi-track strings if given two multi-track strings (multi-sets of strings) $\mathcal{T} = (t_1, t_2,\ldots , t_N)$ and $ \mathcal{P} = (p_1, p_2, \ldots, p_N)$ such that $| p_1 | = | p_2 | = \ldots = | p_N | = | t_1 | = | t_2 | = \ldots = | t_N |$, then there is a full-permuted-match between $\mathcal{P}$ and $\mathcal{T}$ if $\mathcal{P} = (t_{r_1}, t_{r_2},\ldots , t_{r_n})$ for some permutation $(r_1,\ldots,r_N)$ of $(1,\ldots,N)$, we denote this $\mathcal{P}\asymp\mathcal{T}$. Efficient algorithms for some full-permuted match problems on multi-track strings have recently been presented \cite{Hendrian_2019,PSC2016-2,10.1007/978-3-642-35843-2_25}. In this paper we show a reduction from multi-track strings of length $n$ with alphabet size $\sigma_U$ to single-track strings of length $2n-1$ with alphabet size $\sigma_U^N$. Through this reduction we allow any string matching algorithm to be used on multi-track string problems using $\asymp$ as the match relation.