KMP Based Pattern Matching Algorithms for Multi-Track Strings Diptarama, Yohei Ueki, Kazuyuki Narisawa, and Ayumi Shinohara Graduate School of Information Sciences, Tohoku University, Japan {diptarama@shino.,yohei ueki@shino.,narisawa@,ayumi@}ecei.tohoku.ac.jp Abstract. 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 find 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 first algorithm is an exact matching algorithm that runs in O(nN ) time after O(mM )-time preprocessing. The second and third algorithms are filtering 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]. Keywords: string matching, multi-track, KMP algorithm 1 Introduction Pattern matching problem on strings is defined as finding all occurences of a pattern string in a text string. Many of pattern matching algorithms can find occurences of the pattern fast by preprocessing the pattern such as AC automa- ton [1], and KMP algorithm [7], or by constructing data structure from the text such as suffix tree [13], suffix array [9], and position heap [2]. Katsura et al. [5, 6] defined a set (or tuple) of strings be a multi-track string, and formulated the pattern matching problem on multi-track strings, called per- muted pattern matching. In order to solve this problem, they proposed permuted pattern matching algorithms by constructing data structure from text such as multi-track suffix tree [5], multi-track position heap [6], or by preprocessing the the pattern such as AC automaton based algorithm [5]. In this paper, we propose three new algorithms for multi-track pattern match- ing problem, based on KMP algorithm [7]1 . The first one is a full-permuted pat- tern matching algorithm, that we call it MTKMP for short. Second and third are filtering algorithms for multi-track full- and sub- permuted matching problem, respectively. For short, we call them Filter-MTKMP-Full and Filter-MTKMP, respectively. Different with AC automaton based algorithm [5] that constructs 1 We implement MP algorithm for the first algorithm and KMP algorithm for the second and third algorithms. KMP Based Pattern Matching Algorithms ... 101 failure functions for each track of the pattern, our algorithms only construct one failure function for a multi-track pattern. Also, our algorithms match the whole tracks of the pattern to the text instead of matching each track of the text independently. We show that MTKMP runs in O(mM ) time for constructing the failure func- tion, 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 filtering, 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 [5] for full-permuted matching, and Filter-MTKMP works faster on sub-permuted-matching when the alphabet size and the track count of the pattern are large. 2 Preliminaries Let w ∈ Σ n be a string of length n over an alphabet Σ, and σ = |Σ| be the alphabet size. |w| 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 ≤ |w|. In addition, w[: i] = w[1 : i] and w[i :] = w[i : |w|] denotes a prefix 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 ∈ Σ n , and each wi is called the i-th track of W. The length n of a multi-track is denoted by |W|len . The number N of tracks in a multi-track is called track count and denoted by |W|num . 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 ≤ |W|len . Moreover, the prefix and suffix of W are denoted by W[: i] = W[1 : i] and W[i :] = W[i : |W|len ], 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 defined 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 ∃r.X = Y⟨r⟩, and X full-permuted- ◃▹ matches Y, denoted by X = ◃▹ Y, if M = N and ∃r.X = Y⟨r⟩. Throughout the paper, we assume that P is a pattern with |P|num = M and |P|len = m, and T is a text with |T|num = N and |T|len = n. The pattern matching problem on multi-tracks are defined 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 . 102 Diptarama, et al. 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 [1] = 0; 12 while i ≤ m do 13 while j > 0 and P[j]⟨SI (P[1 :])⟩ ̸= P[i]⟨SI (T[i − j + 1 :])⟩ do j = F [j]; 14 i = i + 1; j = j + 1; 15 F [i] = j; In this section, we propose an algorithm for full-permuted pattern match- ing that based on KMP algorithm, named multi-track KMP algorithm (shortly MTKMP). In a similar manner to the original KMP algorithm, MTKMP con- structs 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 defined as the length of the longest proper suffix of P[1 : i − 1] that permuted-matches with a prefix of P, except F [1] = 0 and F [2] = 1. In order to construct the failure function, first MTKMP finds the value of sorted index SI (P[i : m]) for all 1 ≤ i ≤ m. Then permuted-matching of suffix P[j : i] and prefix P[1 : i − j + 1] is performed by using SI (P[1 :]) and SI (P[j :]). MTKMP performs permuted pattern matching from left to right of the pat- tern 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 [3, 10, 12, 13] or suffix array [4, 8, 9, 11]. Next, both the outer while loop and the inner while loop are called O(m) times, since the i − j ≤ i ≤ m + 1 and the value of i always increase each time the outer loop is called, and the value of i − j always increases each time the inner loop is called. Since KMP Based Pattern Matching Algorithms ... 103 Algorithm 2: Filter-MTKMP-Full pattern matching algorithm Input: Multi-track T, Multi-track P 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 if T[i − j + 1 : i − 1] ⊑ P then output (i − j + 1); ◃▹ 8 9 j = F [j]; 10 Function constructFailureFunction() 11 i = 1; j = 1; F [1] = 0; 12 while i ≤ m do 13 while j > 0 and P′ [i] ̸= P′ [j] do j = F [j]; 14 i = i + 1; j = j + 1; 15 if i ≤ m and P′ [i] = P′ [j] then F [j] = F [i]; else F [j] = i; a comparison of P[j]⟨SI (P[1 :])⟩ and P[i]⟨SI (T[i−j +1 :])⟩ consumes O(M ) time, constructFailureFunction function runs in O(M m) time. In a similar way, the search algorithm of MTKMP runs in O(N n) time. 3 KMP Algorithm for Filtering on Multi-Track String In this section we propose two filtering 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 find candidates of permuted-matching positions. Finally, every candidate position is checked whether or not the pattern is permuted-matched in each position. The first algorithm is an algorithm for full-permuted pattern matching prob- lem called Filter-MTKMP-Full. We use two functions in this algorithm. Ge- nerally, we can implement another function that has a false positive property. The second algorithm, Filter-MTKMP is an algorithm for both full- and sub- permuted pattern matching problems. Filter-MTKMP transforms multi-track into alphabet bucket and implements KMP algorithm to it. 3.1 Full-Permuted Pattern Matching Algorithm The Filter-MTKMP-Full algorithm is described in Algorithm 2. First, we trans- form 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(). 104 Diptarama, et al. Definition 1. For Z = (z1 , z2 , . . . , zN ), sort(Z) = Z′ = (z1′ , z2′ , . . . , zN ′ ) such ′ ′ ′ that ∃r.Z [i] = Z[i]⟨r⟩ and zj [i] ≼ zj+1 [i] for 1 ≤ i ≤ |Z|len and 1 ≤ j < N . Definition 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 defined as follows,     abab aaaa   b b a c a a a b 3221     Z=      a a b b  , sort(Z) =  a b b b  , bucket(Z) = 1 3 3 3 .  c a b b b b b b 1001 abba cbbc 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 trans- formed 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 permuted- matched. In the same way as described in MTKMP, the failure function can be con- structed in O(m(M + σ)) time and the filtering algorithm runs in O(n(N + σ)) time, since sort() and bucket() needs O(M ) and O(σ) time for each compari- son, 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 Permuted Pattern Matching Algorithm Filter-MTKMP algorithm is an extended version of the Filter-MTKMP-Full al- gorithm that can be applied to the sub-permuted pattern matching problem. This algorithm uses bucket() to transforms the pattern and the text, and imple- ment 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 finds candidates of matched position by using the failure function. Last, in the similar way as Filter-MTKMP-Full, the Filter-MTKMP algo- rithm runs in O(m(M + σ)) time for constructing the failure function, O(n(N + KMP Based Pattern Matching Algorithms ... 105 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 if T[i − j + 1 : i − 1] ⊑ P then output (i − j + 1); ◃▹ 8 9 j = F [j]; 10 Function constructFailureFunction() 11 i = 1; j = 1; F [1] = 0; 12 while i ≤ m do 13 while j > 0 and diff (P′ [i], P′ [j]) > N − M do j = F [j]; 14 i = i + 1; j = j + 1; 15 if i ≤ m and P′ [i] = P′ [j] then F [j] = F [i]; else F [j] = i; 16 Function diff (Vector X, Vector Y ) 17 Int sum = 0; 18 for k = 1 to |X| do 19 sum = sum + max(0, Y [k] − X[k]); 20 return sum; σ)) time for finding candidates, and O(cmM ) time for checking the candidates, where c is the number of candidates. 4 Experiments In order to evaluate the performance of proposed algorithms, we conduct experi- ments and compare the running time of proposed algorithms with AC automaton based algorithm [5]. In the first 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 au- tomaton based algorithm. However, many false positive candidates are found when the length of the pattern is short, and filtering algorithms need lots of time to verify them. 106 Diptarama, et al. Fig. 1. Running time of the algorithms on full-permuted pattern matching with respect to (a) text length, (b) track count, (c) pattern length, and (d) alphabet size. The second experiment measures the running time of Filter-MTKMP on sub- permuted 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 Fig. 2. Running time of the algorithms on sub-permuted pattern matching with respect to (a) pattern track and (b) alphabet size. KMP Based Pattern Matching Algorithms ... 107 track count of the text and track count of the pattern is small, also when the alphabet size is large. 5 Conclusion We proposed three algorithms based on the KMP algorithm, that are MTKMP, Filter-MTKMP-Full and Filter-MTKMP. These algorithms can solve the per- muted pattern matching problem in linear time. We also conducted compu- tational 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. References 1. Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Communications of the ACM 18(6) 333–340 (1975) 2. Ehrenfeucht, A., McConnell, R.M., Osheim, N., Woo, S.W.: Position heaps: A simple and dynamic text indexing data structure. Journal of Discrete Algo- rithms 9(1) 100–121 (2011) 3. Farach, M.: Optimal suffix tree construction with large alphabets. In: FOCS. 137–143 (1997) 4. Kärkkäinen, J., Sanders, P.: Simple linear work suffix array construction. In: ICALP. 943–955 (2003) 5. Katsura, T., Narisawa, K., Shinohara, A., Bannai, H., Inenaga, S.: Permuted pattern matching on multi-track strings. In: SOFSEM. 280–291 (2013) 6. Katsura, T., Otomo, Y., Narisawa, K., Shinohara, A.: Position heaps for permuted pattern matching on multi-track strings. In: Proceedings of Student Research Forum Papers and Posters at SOFSEM 2015. 41–531 (2015) 7. Knuth, D.E., Jr., J.H.M., Pratt, V.R.: Fast pattern matching in strings. SIAM Journal on Computing 6(2) 323–350 (1977) 8. Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. In: CPM. 200–210 (2003) 9. Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing 22(5) 935–948 (1993) 10. McCreight, E.M.: A space-economical suffix tree construction algorithm. Journal of the ACM 23(2) 262–272 (1976) 11. Nong, G., Zhang, S., Chan, W.H.: Linear suffix array construction by almost pure induced-sorting. In: Data Compression Conference. 193–202 (2009) 12. Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3) 249–260 (1995) 13. Weiner, P.: Linear pattern matching algorithms. In: SWAT. 1–11 (1973)