A Simple Reduction for Full-Permuted Pattern Matching Problems on Multi-Track Strings
share
In this paper we study a variant of string pattern matching which deals with tuples of strings known as multi-track strings. Multi-track strings are a generalisation of strings (or single-track strings) that have primarily found uses in problems related to searching multiple genomes and music information retrieval Lemstrom:2003:MPS:1756553.1756571,Lemstrom:2003:TIP:967792.967793. There is a full-permuted-match between two multi-track strings if given two multi-track strings (multi-sets of strings) T = (t_1, t_2,... , t_N) and P = (p_1, p_2, ..., p_N) such that | p_1 | = | p_2 | = ... = | p_N | = | t_1 | = | t_2 | = ... = | t_N |, then there is a full-permuted-match between P and T if P = (t_r_1, t_r_2,... , t_r_n) for some permutation (r_1,...,r_N) of (1,...,N), we denote this PT. Efficient algorithms for some full-permuted match problems on multi-track strings have recently been presented 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 σ_U to single-track strings of length 2n-1 with alphabet size σ_U^N. Through this reduction we allow any string matching algorithm to be used on multi-track string problems using as the match relation.
READ FULL TEXT