Multi-track string is an N -tuple strings of length n. For two multi-track strings T = (t1; t2; : : : ; tN ) of length n and P = (p1; p2; :::; pM ) of length m, permuted pattern matching is a problem to nd all positions i such that P is permuted match with T[i : i + M ]. We propose three new algorithms for permuted pattern matching based on the KMP algorithm. The rst algorithm is an exact matching algorithm that runs in O(nN ) time after O(mM )-time preprocessing. The second and third algorithms are ltering algorithms that run in O(n(N + )) after O(m(M + ))time preprocessing, where is the size of alphabet. Experiments show that our algorithms run faster than AC automaton based algorithm that proposed by Katsura et al. [5].
Pattern matching problem on strings is de ned as nding all occurences of
a pattern string in a text string. Many of pattern matching algorithms can nd
occurences of the pattern fast by preprocessing the pattern such as AC
automaton [
Katsura et al. [
In this paper, we propose three new algorithms for multi-track pattern
matching problem, based on KMP algorithm [
We show that MTKMP runs in O(mM ) time for constructing the failure
function, and O(nN ) for matching. Both Filter-MTKMP-Full and Filter-MTKMP
run in O(m(M + )) time for constructing the failure function, O(n(N + )) for
ltering, and O(mM ) to verify each candidate. Moreover, the experiment results
show that proposed algorithms run faster than AC automaton based multi-track
pattern matching algorithm [
Let w 2 n be a string of length n over an alphabet , and = j j be the alphabet size. jwj denotes the length of w and w[i] denotes i-th character of w. The substring of w that begins at position i and ends at position j is denoted by w[i : j] for 1 i j jwj. In addition, w[: i] = w[1 : i] and w[i :] = w[i : jwj] denotes a pre x and a suffix of w, respectively. For two strings x and y, x ≺ y denotes that x is lexicographically smaller than y, and x ≼ y denotes that either x equals to y or x ≺ y.
A multi-track string (or multi-track for short) W = (w1; w2; :::; wN ) is an N -tuple of strings wi 2 n, and each wi is called the i-th track of W. The length n of a multi-track is denoted by jWjlen . The number N of tracks in a multi-track is called track count and denoted by jWjnum . For two multi-tracks X = (x1; x2; ::; xN ) and Y = (y1; y2; ::; yN ), we write X = Y if xi = yi for 1 i N . W[i] denotes (w1[i]; w2[i]; :::wN [i]), and W[i : j] denotes (w1[i : j]; w2[i : j]; : : : ; wN [i : j]) for 1 i j jWjlen . Moreover, the pre x and suffix of W are denoted by W[: i] = W[1 : i] and W[i :] = W[i : jWjlen ], respectively.
Let r = (r1; r2; : : : ; rM ) be a partial permutation of (1; 2; : : : ; N ) for M N . For a multi-track W = (w1; w2; : : : ; wN ), a permuted multi-track of W is denoted by either W⟨r1; r2; : : : ; rM ⟩ or W⟨r⟩. Sorted index of a multi track SI(W) = (r1; r2; : : : ; rN ) is de ned as a permutation such that wri ≼ wrj for any 1 i j N . For two multi-tracks X = (x1; x2; : : : ; xM ) and Y = (y1; y2; : : : ; yN ), X ◃▹ permuted-matches Y, denoted by X ⊑ Y, if 9r:X = Y⟨r⟩, and X full-permutedmatches Y, denoted by X =◃▹ Y, if M = N and 9r:X = Y⟨r⟩.
Throughout the paper, we assume that P is a pattern with jPjnum = M and jPjlen = m, and T is a text with jTjnum = N and jTjlen = n. The pattern matching problem on multi-tracks are de ned as follows.
Problem 1 (Permuted pattern matching). Given a multi-tracks text T and a multi-track pattern P, output all positions i that satisfy P ⊑◃▹ T[i : i + m 1]. Moreover, we call it full-permuted pattern matching if M = N , and sub-permuted pattern matching if M < N .
Algorithm 1: MTKMP pattern matching algorithm
Input: Multi-track T, Multi-track P
Output: match positions
1 compute SI (T[i :]) for 1 i n and SI (P[i :]) for 1 i m;
2 constructFailureFunction();
3 i = 1; j = 1;
4 while i n do
5 while j > 0 and T[i]⟨SI (T[i j + 1 :])⟩ ̸= P[j]⟨SI (P[1 :])⟩ do j = F [j];
6 i = i + 1; j = j + 1;
7 if j > m then
8 output (i j + 1);
9 j = F [j];
10 Function constructFailureFunction()
11 i = 1; j = 1; F [
In this section, we propose an algorithm for full-permuted pattern matching that based on KMP algorithm, named multi-track KMP algorithm (shortly MTKMP). In a similar manner to the original KMP algorithm, MTKMP constructs the failure function from the pattern, then uses it to shift the pattern when mismatch occurs. The MTKMP algorithm is described in Algorithm 1.
The failure function F [i] for 1 i m+1 in MTKMP is de ned as the length
of the longest proper suffix of P[1 : i 1] that permuted-matches with a pre x of
P, except F [
MTKMP performs permuted pattern matching from left to right of the pattern and the text. Sorted indexes of the text and the pattern are used to perform permuted-matching between the pattern and a substring of the text. If characters on text and pattern are mismatched, then we shift the position of the pattern by using the failure function. If the pattern matches a substring of the text, then MTKMP outputs the position of the text and shifts the pattern according to the failure function.
The MTKMP algorithm runs in O(mM ) time for constructing the failure
function and O(nN ) time for matching. Suffix index SI (P[i :]) for 1 i m
and SI (T[i :]) for 1 i n can be computed in O(mM ) and O(nN ) respectively
by using suffix tree [
Output: match position
1 T′ = func(T); P′ = func(P);
2 constructFailureFunction();
3 i = 1, j = 1;
4 while i n do
5 while j > 0 and T′[i] ̸= P′[j] do j = F [j];
6 i = i + 1; j = j + 1;
7 if j > m then
8 if T[i j + 1 : i 1] ⊑◃▹ P then output (i j + 1);
9 j = F [j];
10 Function constructFailureFunction()
11 i = 1; j = 1; F [
In this section we propose two ltering algorithms that can outperform MTKMP for permuted pattern matching problems. Instead of the suffix index, we use simple functions to transforms the multi-track string, that can be computed faster than the suffix index. Then, by transforming the pattern and the text, the KMP algorithm can be applied to nd candidates of permuted-matching positions. Finally, every candidate position is checked whether or not the pattern is permuted-matched in each position.
The rst algorithm is an algorithm for full-permuted pattern matching problem called Filter-MTKMP-Full. We use two functions in this algorithm. Generally, we can implement another function that has a false positive property. The second algorithm, Filter-MTKMP is an algorithm for both full- and subpermuted pattern matching problems. Filter-MTKMP transforms multi-track into alphabet bucket and implements KMP algorithm to it. 3.1
The Filter-MTKMP-Full algorithm is described in Algorithm 2. First, we transform P by a function func() that has a false-positive property, that is if X =◃▹ Y then func(X) = func(Y). We propose two functions, sort () and bucket ().
De nition 1. For Z = (z1; z2; : : : ; zN ), sort (Z) = Z′ = (z1′; z2′; : : : ; zN′ ) such that 9r:Z′[i] = Z[i]⟨r⟩ and zj′[i] ≼ zj′+1[i] for 1 i jZjlen and 1 j < N . De nition 2. For Z = (z1; z2; : : : ; zN ), bucket (Z) = (b1; b2; : : : ; b ) such that bj[i] is the number of the lexicographical j-th character in Z[i].
For example, for a multi-track Z = (abab; bbac; aabb; cabb; abba), the sort (Z) and bucket (Z) are de ned as follows, 0 a b a b 1 0 a a a a 1
B b b a c C B a a a b C 0 3 2 2 1 1 Z = BB a a b b CC ; sort (Z) = BB a b b b CC ; bucket (Z) = @ 1 3 3 3 A : B@ c a b b CA B@ b b b b CA 1 0 0 1
a b b a c b b c For a multi-track Z, sort (Z) can be computed in O(n(N + )) by using the bucket sorting algorithm, and bucket (Z) can be computed in O(nN ) time by counting all characters in Z even if naively.
Next, Filter-MTKMP-Full constructs the failure function F of the transformed multi-track P′ by similar algorithm as the KMP algorithm.
Pattern matching in Filter-MTKMP-Full is performed on P′ and T′. When unmatched is occurred, the pattern is shifted by using the failure function. If P′ matches to T′[i : j], then the algorithm checks whether the pattern P is permuted-matched with T[i : j] or not, and outputs it if the pattern is permutedmatched.
In the same way as described in MTKMP, the failure function can be constructed in O(m(M + )) time and the ltering algorithm runs in O(n(N + )) time, since sort () and bucket () needs O(M ) and O( ) time for each comparison, respectively. Also, the Filter-MTKMP-Full algorithm runs in O(m(M + )) time for constructing the failure function. In addition, Filter-MTKMP-Full need O(cmM ) time for checking the candidates, where c is the number of candidates. 3.2
Filter-MTKMP algorithm is an extended version of the Filter-MTKMP-Full algorithm that can be applied to the sub-permuted pattern matching problem. This algorithm uses bucket () to transforms the pattern and the text, and implement the KMP algorithm to the transformed pattern and text. Moreover, this algorithm uses diff (X; Y ) function instead of X ̸= Y to loosen the condition, thus sub-permuted pattern matching can be performed.
Algorithm 3 shows a pseudocode of the Filter-MTKMP algorithm. First, it transforms P to multi-track bucket P′ and constructs the failure function F of the multi-track bucket by using a function diff (X; Y ) = ∑i=1 max(0; Y [i] X[i]) for two integer vectors X and Y . Then, it nds candidates of matched position by using the failure function.
Last, in the similar way as Filter-MTKMP-Full, the Filter-MTKMP algorithm runs in O(m(M + )) time for constructing the failure function, O(n(N + Algorithm 3: Filter-MTKMP pattern matching algorithm
Input: Multi-track T, Multi-track P
Output: match position
1 T′ = bucket (T); P′ = bucket (P);
2 constructFailureFunction();
3 i = 1; j = 1;
4 while i n do
5 while j > 0 and diff (P′[j]; T′[i]) > 0 do j = F [j];
6 i = i + 1; j = j + 1;
7 if j > m then
8 if T[i j + 1 : i 1] ⊑◃▹ P then output (i j + 1);
9 j = F [j];
10 Function constructFailureFunction()
11 i = 1; j = 1; F [
X[k]); 20
return sum; )) time for nding candidates, and O(cmM ) time for checking the candidates, where c is the number of candidates. 4
In order to evaluate the performance of proposed algorithms, we conduct
experiments and compare the running time of proposed algorithms with AC automaton
based algorithm [
In the rst experiment, we compare running time of the algorithms for solving full-permuted pattern matching. We change one of the parameters while keeping other parameters constant. We set constant parameter as follows, n = 100000, m = 10, N = M = 1000, and = 2. We use random text and pattern with 50 occurrences of the pattern inserted to the text. Figure 1 (a)-(d) show running time of the algorithms when one of the parameters n, N , m, and is changed respectively. We can see that the proposed algorithms are faster than AC automaton based algorithm. However, many false positive candidates are found when the length of the pattern is short, and ltering algorithms need lots of time to verify them.
The second experiment measures the running time of Filter-MTKMP on subpermuted pattern matching, and compares it with AC automaton algorithm. We set n = 10000, N = 1000, m = 10, M = 600, and = 26 as constant parameters. Figure 2 (a) and (b) show that running time of Filter-MTKMP is decreased when the track count of the pattern and the alphabet size are increased, because the number of false-positive candidates are decreased if the track count is increased. We can conclude that Filter-MTKMP performs better if the difference between track count of the text and track count of the pattern is small, also when the alphabet size is large. 5
We proposed three algorithms based on the KMP algorithm, that are MTKMP, Filter-MTKMP-Full and Filter-MTKMP. These algorithms can solve the permuted pattern matching problem in linear time. We also conducted computational experiments, and showed that proposed algorithms work faster than AC-automaton based algorithm.
Acknowledgments. This work was partly supported by KAKENHI Grant Numbers 15H05706, 25560067 and 25240003. This work was also supported by research grant and scholarship from Tohoku University Division for International Advanced Research and Education.