A multi-set of N strings of length n is called a multi-track string. The permuted pattern matching is the problem that given two multi-track strings T = ft1; : : : ; tN g of length n and P = fp1; : : : ; pN g of length m, outputs all positions i such that fp1; : : : ; pN g = ft1[i : i + m 1]; : : : ; tN [i : i + m 1]g We propose two new indexing structures for multi-track stings. One is a time-e cient structure for T that needs O(nN ) space and enables us to solve the problem in O(m2N + occ) time, where occ is the number of occurrences of the pattern P in the text T. The other is memory-e cient, it requires only O(n) space, whereas the matching consumes O(m2N 2 + occ) time. We show that both of them can be constructed in O(nN ) time.
The string indexing problem is fundamental and important for information
retrieval, and to build an index for a given length n text string that allows us to
nd all occurrences of a given length m pattern string in the text e ciently. The
classical indexing structures, su x trees [
Ehrenfeucht et al. [
Kucherov [?] showed an Ukkonen-like on-line O(n)-time algorithm for
constructing position heaps. By using position heaps, the occurrences of the
pattern can be found in O(m2 + occ) time. To improve its time bound to O(m +
occ), Ehrenfeucht et al. [
Recently, Katsura et al. [
To solve this problem e ciently, Katsura et al. proposed an indexing structure for multi-track strings, called multi-track su x trees (shortly MTST). MTST can be built in O(nN ) time and space, and it provides an O(mN + occ)-time matching algorithm. MTST has most 2n 1 nodes.
Note that another well-known indexing structure generalized su x tree (GST) is also applicable to the problem. By a natural extension, the matching can be done in O(mN + occ) time. The space complexity is also O(nN ), but the number of nodes is at most 2nN 1.
In this paper, we propose two new memory e cient indexing structures for multi-track strings, multi-track position heap (MTPH) and contracted multi-track position heap (CMTPH).
CMTPH is a compact version of MTPH, where some nodes are rearranged and omitted. The number of nodes in MTPH and CMTPH is at most nN + 1 and n + 1, respectively, although the input size of the multi-track text is nN .
The permuted pattern matching using MTPH or CMTPH requires O(m2N + occ) or O(m2N 2 + occ) time, respectively. Moreover, for MTPH and CMTPH, we de ne the MRPs to accelarate the matching.
We show O(nN )-time construction algorithms for MTPH and CMTPH with their MRPs. The contributions of this paper is summarized in Table 1. 2
Let be a nite set of characters, called an alphabet. We assume that is xed throughout the paper. An element of is called a string. For two strings x and y, let x y, or xy brie y, be the concatenation of x and y. For a string w = xyz, strings x, y, z are called pre x, substring, su x of w, respectively. jwj is the length of w. The empty string is denoted by ", that is j"j = 0. w[i] is the i-th character of w, and w[i : j] is the substring of w that begins at position i and ends at j for 1 i j jwj. Moreover, let w[: i] = w[1 : i] and w[i :] = w[i : jwj]. We denote by x y if x is lexicographically smaller than y, and denote by x y if either x y or x = y. For a set S, we denote by jSj the cardinality of S. An N -tuple 1 of strings over of length n is called a multi-track string over or simply multi-track.
For a multi-track T = (t1; t2; : : : ; tN ) over , the i-th element ti of T is called the i-th track, the length of multi-track T is denoted by jTjlen = jt1j = jt2j = = jtN j = n, and the number of tracks in multi-track T or the track count of T, is denoted by jTjnum = N . For two multi-tracks X = (x1; x2; : : : ; xN ) and Y = (y1; y2; : : : ; yN ), we say that X equals Y, denoted by X = Y, if xi = yi for all 1 i N .
For a multi-track T = XYZ, multi-track X, Y, and Z are called pre x,
substring, and su x of T, respectively. T[i] denotes (t1[i]; t2[i]; : : : ; tN [i]) for 1 i
jTjlen, i.e., T = T[
Let X = (x1; x2; : : : ; xN ) be a multi-track of track count N , and r = (r1; r2; : : : ; rN ) be a permutation of (1; : : : ; N ). A permuted multi-track of X speci ed by r is a multi-track (xr1 ; xr2 ; : : : ; xrN ), denoted by either Xhr1; r2; : : : ; rN i or Xhri. For two multi-tracks X and Y, we say that X permuted-matches Y, denoted by X =./ Y, if X = Y0 for some permuted multi-track Y0 of Y. The problem we consider is de ned as following: Problem 1 (Permuted pattern matching). Given two multi-tracks T = (t1; t2; : : : ; tN ) of length n and P = (p1; p2; : : : ; pN ) of length m, output all positions i that satisfy P =./ T[i : i + m 1].
For a multi-track X = (x1; x2; : : : ; xN ), let SI (X) = (r1; r2; : : : ; rN ) be
a permutation such that xri xrj for any 1 i j jXjnum, and let
(X) = XhSI (X)i. All SI (T[i :]) for 1 i n and (T) can be computed
in O(nN ) time using the su x tree [
A trie on is a rooted tree that has the following two properties: (1) each
edge is labeled by a character c 2 , and (2) for each node u and a character
c 2 , u has at most one edge that is labeled by c from u to a child of u. Let
T = (V; E) be a trie, where V and E are sets of nodes and edges, respectively.
The root node of T is denoted by root . Each edge e 2 E is denoted by (u; c; v),
where c 2 is the label of e, and v is a child node of a node u. Note that the
time required to nd the child of a node on the child edge labeled by c 2
is O(log j j). Because j j is a xed constant in this paper, so that the above
time cost is also constant. For a node v 2 V , the sequence of nodes and edges
from root to v, that is root ; e1; v1; e2; v2; : : : ; ek; v, is called the path from root to
1 A multi-track string was regarded as a multi-set of strings in [
Thus, root = " and label (root ) = ". For any node v in T , the set of ancestors of v is denoted by Anc(v) and the descendants of v by Des(v).
A sequence hash tree [
De nition 1 (Sequence hash trees [
qi is the shortest pre x of wi satisfying qi 2= Vi 1, and c = qi[jqij]. SHT k(W ) is called a sequence hash tree of W and denoted by SHT (W ).
For any i, SHT i(W ) is obtained by adding at most one node and one edge. Thus, SHT (W ) = SHT k(W ) consumes O(k) space. SHT i(W ) is obtained by adding a node corresponding to wi into SHT i 1(W ). When the node corresponding to wi is added into SHT i 1(W ), we say that wi is inserted to SHT i 1(W ). Lemma 1. Let W = fw1; w2; : : : ; wK g and W 0 = fw10; w20; : : : ; wk0g (k K) be ordered sets of strings such that W 0 is a subset of W . Then SHT (W 0) is a subtree of SHT (W ) rooted by the root of SHT (W ).
inserted to SHT (W 0), and let d = depth(v). Then there exist 1 i1 < i2 < : : : < id 1 k such that the strings wi01 , wi02 , : : :, wi0d 1 precede w in W 0, and wi0j [: j] = w[: j] holds for each 1 j d 1. These strings also precede w in W , because W 0 is a subset of W . Thus, wi01 , wi02 ; : : : ; wi0d 1 , and w are inserted to
to SHT (W ) if w[: j] does not exist in SHT (W ) for 1 j d 1. Therefore, when w is inserted to SHT (W ), w[: d 1] has already been represented in SHT (W ) and w[: d] is added to SHT (W ). As a result, any string represented in SHT (W 0) is also represented in SHT (W ), so that the statement holds.
We use the following results for the rooted tree T of n nodes and tu degree.
Lemma 2 (Lowest common ancestor query [
Lemma 4 (Level ancestor query [
CST = t1[
For instance, for T = (abac; deba), we have CST = adbeabca.
De nition 2 (MTPH). Let T be a multi-track string of length n and track count N over . Let si;j = CS (T[i:j]) for 1 i j n, and si;n is denoted by si brie y. Let S = fs1; s2; : : : ; sng be an ordered set of the strings. For 1 i n, MTPH i(T) = (Vi; Ei) is a trie recursively de ned by (V0; E0) = (froot g; ;), and Vi = Vi 1 [ Sj=i0 1 fsi[: jqij + j]g, Ei = Ei 1 [ Sj=i0 1f(si[: jqij + j 1]; si[jqij + j]; si[: jqij + j])g), where qi is the shortest pre x of si such that qi 2= Vi 1 and qi 6= ", and i = N ((jqij 1) mod N ). If no such qi exists, that is si 2 Vi 1, then (Vi; Ei) = (Vi 1; Ei 1). MTPH n(T) is called a multi-track position heap of T, and denoted by MTPH (T).
Figure 1 shows an example of MTPH (T) and column concatenated strings.
Both the numbers of nodes and edges of MTPH i(T) increase at most N from MTPH i 1(T) for each 1 i n. Thus, MTPH (T) consumes O(nN ) space. If there exists qi, then we associate the position i to the node si[: jqij + i 1], and call it an indexing node. Otherwise, that is si 2 Vi 1, we associate i to the node si. Therefore, each indexing node stores either one or two positions. In case that an indexing node v stores two positions i and j with i < j, we call that i is the primary position and j is the secondary position in v.
We will show that MTPH (T) can be constructed in O(nN ) time by updating
MTPH (T[: i 1]) to MTPH (T[: i]) iteratively for i = 1; 2; : : : ; n, similar to the
online construction algorithm for position heaps [
Let j (1 j < i) be any secondary position in a node v in MTPH (T[: i 1]). If the string sj;i is not represented in MTPH (T[: i 1]) yet, then we create a new path path(root ; sj ;i ) and reset the position j from v to a newly created node sj;i. Otherwise, the position j must be a secondary in another existing node v0 in MTPH (T[: i]). Thus, we should reset j from v to v0 = sj;i. These update process can be done by traversing the nodes storing the secondary positions.
We will show that for any position b (1 b < i), if b is a secondary position then b + 1 is also a secondary position, by a series of lemmas as follows. Lemma 5. For two multi-tracks X = (x1; x2; : : : ; xN ) and Y = (y1; y2; : : : ; yN ), if (X) = (Y) then (X[2 :]) = (Y[2 :]).
Proof. Trivial.
Lemma 6. For any multi-track W of length m, if CS (W) is represented in MTPH i(T), then CS (W[2:]) is also represented in MTPH i(T) for any 1 i n. Proof. Because CS (W) is represented in MTPH i(T), there are 1 j1 j2 : : : jm i such that (T[jk : jk + k 1]) = (W[: k]) for 1 k m, and they have been inserted to MTPH in the order of k = 1; 2; : : : ; m. At the same time, (T[jk + 1 : jk + k 1]) for 1 k m have also been inserted in this order, because MTPH is constructed by inserting su xes in descending order with respect to the length. Lemma 5 leads (T[jk + 1 : jk + k]) = (W[2 : k]). Thus, CS (T[jm+1:jm+m]) = CS (W)[2:] is represented in MTPH i(T ): tu Lemma 7. If b is a secondary position of a node v in MTPH i(T) for 1 then b + 1 is also a secondary position of another node in it. b < i, Proof. Let b0 be the primary position of v. Then, b0 < b and sb = sb0 [: jsbj] hold.
is also represented. From Lemma 5, sb+1 = sb0+1[: jsb+1j] holds. Since b0 < b, b0 + 1 < b + 1. Thus, b + 1 is a secondary position of sb0+1.
Let b be the smallest position that is a secondary position in MTPH (T[: i 1]) with 1 b i 1. By Lemma 7, all the secondary positions are written as b; b + 1; : : : ; i 1. In addition, these positions are partitioned into two intervals. Let b0 be the smallest position such that sb0;i is represented in MTPH (T[: i 1]). Then, sb0+1;i is also represented in it by Lemma 6. Similarly, all sb0+2;i; : : : ; si 1;i are represented in it, too. Therefore, all the positions b; b+1; : : : ; b0 1 in the rst tu tu interval are primary positions in MTPH (T[: i]), while all b0; b0 + 1; : : : ; i 1 in the second interval are secondary positions in MTPH (T[: i]). Summarizing the above discussion, to obtain MTPH (T[: i]), MTPH (T[: i 1]) should be updated as follows: (1) for b j < b0, build path(sj ;i 1 ; sj ;i ) and reset the position j from sj;i 1 to the new node sj;i as its primary position, and (2) for b0 j i, reset the position j from sj;i 1 to the existing node sj;i as its secondary position. We refer the position b as the active position, and the indexing node sb;i 1 as the active node, similarly to [?]. The nodes storing positions b; b + 1; : : : ; i 1 can be traversed e ciently by using the su x pointers de ned below. De nition 3 (Multi-track su x pointers). For any indexing node si;j in MTPH (T), the multi-track su x pointer of si;j is a pointer from si;j to the node si+1;j, and denoted as mtsp(si;j) = si+1;j.
For every indexing node si;j in MTPH (T[: i]), the existence of mtsp(si;j)
is guaranteed by Lemma 6. In our algorithm, we will use a chain of N nodes
?1; ?2; : : : ; ?N , such that each ?k (1 k N ) is connected to ?k+1 by an
edge labeled by all c 2 , regarding that ?N+1= root , and mtsp(root ) =?1.
They play a role of sentinel nodes, similarly to [
We now describe the construction algorithm of MTPH (T). First of all, we compute SI (T[i : n]) for all 1 i n in O(nN ) time. It determines every si = CS (T[i:]). In each iteration, we do not need to keep all the secondary nodes to update MTPH (T[: i 1]), because these nodes can be visited through the su x pointers recursively from the active node. Thus, we only maintain the active position b and the active node sb;i 1. If there is no secondary node in MTPH (T[: i 1]), the active node is root and the active position is i.
In i-th iteration, the algorithm checks whether there is path(sb;i 1 ; sb;i ) or not. If it does not exist, the algorithm performs the modi cations of Case (1) described above. After the modi cation, the new indexing node sb;i is created as a descendant of sb;i 1. Then, the active position and the active node are updated to b + 1 and mtsp(sb;i 1) = sb+1;i 1 respectively, and the algorithm performs the above process iteratively until the path is found. The multi-track su x pointer mtsp(sb;i) is built as mtsp(sb;i) = sb+1;i after the next modi cation. When path(sb;i 1 ; sb;i ) is found, the algorithm updates the active node to sb;i and makes the su x pointer from the last created indexing node to the new active node if such a node exists. Hence, for any indexing node, su x pointer of it is de ned indeed. To update MTPH (T[: i 1]) into MTPH (T[: i]), it is enough to perform only the modi cations of Case (1), because the modi cations of Case (2) does not add any node nor edge to MTPH. All the secondary positions will be determined after constructing MTPH (T) by traversing nodes through the su x pointers recursively from the active node.
Algorithm 1 shows a pseudo-code of the construction algorithm, and the function to nd path(sb;i 1 ; sb;i ) at line 26. Let us analyze the running time of Algorithm 1. Each iteration of the while-loop from line 9 takes O(nN ) time over the whole run of the algorithm, because at most N nodes and edges are visited or created in each iteration and 1 b n. Each process in the rest of
Algorithm 1: MTPH construction algorithm
Input: T
Output: MTPH (T) 1 compute SI (T[i : n]) for all 1 i n; 2 create root and ?N ; create edge (?N ; c; root ) for each character c; 3 for j = N 1 downto 1 do 4 create node ?j; create edge (?j; c; ?j+1) for each character c; 5 mtsp(root ) =?1; activeNode = root ; b = 1; 6 for i = 1 to n do 7 lastNode = unde ned; 8 targetNode = nd (activeNode; sb [depth(activeNode)+1 :]); 9 while targetNode = unde ned do 10 for j = 1 to N do 11 u = activeNode; 12 if there is not an edge labeled by w[j] from u then 13 create a node v and an edge (u; w[j]; v) where
label (v) = label (u) w[i]; else u = v;
Let v be a child of u connected by the edge (u; w[j]; v); if lastNode 6= unde ned then mtsp(lastNode) = u; lastNode = u; Let lastNode store b; activeNode = mtsp(activeNode); b = b + 1; targetNode = nd (activeNode; sb [depth(activeNode)+1 :]); activeNode = targetNode; if lastNode 6= unde ned then mtsp(lastNode) = activeNode; 23 if b 6= n + 1 then 24 for b j n do 25 Let activeNode store j ; 26 Function nd (node; w ) 27 for j = 1 to N do 28 if exist edge (node; w[j]; v) then node = v; 29 else return unde ned; 30 return node;
activeNode = mtsp(activeNode); the for-loop from line 6 takes at most O(N ) time, and the loop iterates exactly n times. Thus, the running time of Algorithm 1 is O(nN ) time. Theorem 1. Algorithm 1 constructs MTPH (T) in O(nN ) time and space. We now consider to solve Problem 1 for a pattern P by using MTPH (T). Let w be the longest pre x of CS (P) represented in MTPH (T). We can compute w in O(mN ) time by traversing path(root ; w ). If w = CS (P), all the positions stored in the nodes of the subtree rooted by w are the occurrences of the pattern P in T. We will deal with enumerating all these positions later. Before it, remark Algorithm 2: Adding maximal reach pointers for MTPH
Input: Tand MTPH (T) with multi-track su x pointers 1 currNode = root; pointerNode = root; ` = 1; 2 for i = 1 to n do 3 while currNode has an outgoing edge labeled by si[`] and ` < jsij do 4 currNode = si[: `]; 5 if currNode is an indexing node then pointerNode = currNode; 6 ` = ` + 1; mrp( i) = currNode; currNode = mtsp(pointerNode); pointerNode = currNode; ` = depth(currNode); that we should also consider another type of occurrences; let I be the set of positions stored in the nodes on path(root ; w ). These are also candidates for the occurrences. Because path(root ; w ) contains at most m indexing nodes, jIj = O(m). For each i 2 I, we check whether P =./ T[i : i + m 1] or not by simply comparing CS (P) with si;i+m 1 = CS (T[i:i+m 1]), and report it if it does. Both the computation of si;i+m 1 and the comparison are done in O(mN ) time.
We now explain how to enumerate all the positions in the nodes of the subtree rooted by w, in case that w = CS (P). Let i be an indexing node that stores the position i in MTPH (T). To obtain these positions e ciently in O(occ) time, we construct another tree T consists only of indexing nodes i's in MTPH (T), where a node i is a child of another node j in T if and only if i 2 Des( j ) and no other indexing node exists between i and j in MTPH (T). Obviously, T can be built by depth- rst-traversal of MTPH (T) in O(nN ) time, and by traversing the subtree of T rooted by the node w, we can enumerate all matched positions in O(occ) time. Thus, we can determine all the positions i such that P =./ T[i : i + m 1] in O(m2N + occ) time.
We now show that the matching by using MTPH can be accelerated by adding
maximal-reach pointers (shortly MRPs). MRPs are the auxiliary structures for
standard position heaps proposed by Ehrenfeucht et al. [
De nition 4 (MRPs for MTPHs). For an indexing node i storing i in MTPH (T), the maximal-reach pointer of i is a pointer from i to si[: `i], and denoted by mrp( i) = si[: `i], where si[: `i] is the longest pre x of si = CS (T[i:]) represented in MTPH (T).
Algorithm 2 is an algorithm for adding MRPs to MTPH, that is based on Kucherov's algorithm for standard position heaps [?]. First of all, the algorithm preprocesses MTPH (T) so that for any node v, it can obtain the depth of v in O(1) time, by assigning unique numbers to the nodes by the depth rst traversal. In i-th iteration between line 2 and line 8, it adds a pointer mrp( i) = si[: `i], where si[: `i] is determined as follows: beginning by currNode = root , it goes down to a child si[: `] of depth(currNode) ` jsij until either currNode does not have a child si[: `] or ` = jsij holds (line 3 to line 6). Then, mrp( i) is obtained as si[: `i] (line 7). The next i+1-th iteration begins at mtsp(pointerNode), where pointerNode is the deepest indexing node visited in the i-th iteration and computed in line 5. Note that, the process of line 5 can be computed in constant time because whether currNode is an indexing node or not is determined by depth(currNode) mod N = 0 or not.
Let us consider the time complexity of Algorithm 2. Each process of line 1, line 7 and line 8 can be done in O(1) time, so that these processes take O(n) time in total. Let us consider the number of executions of while-loop at line 3. In each loop, si[`] corresponding to a letter in the text T is read. We assume si[`i] belongs to k-th column of T for 1 k n. k does not decrease between i-th and (i + 1)-th iterations because (i + 1)-th iteration begins at mtsp(si;k) = si+1;k. In addition, since jsi[`i]j N , i k holds. Thus, all letters in T are read at least one time in all iterations. On the other hand, the letters corresponding to the labels on path(pointerNode; currNode) in i-th iteration can be read redundantly in (i + 1)-th iteration. However, the number of such labels does not exceed N in each iteration. Therefore, the total number of executions of while-loop does not exceed 2nN . As a result, the running time of Algorithm 2 is O(nN ) time.
In the naive matching algorithm with MTPH described above, the cost of the comparison of CS (P) with si;i+m 1 for i 2 I can be reduced from O(mN ) to O(1) by using the MRPs and the lowest common ancestor queries mentioned in Lemma 4, if CS (P) itself is represented in MTPH (T). Whether CS (P) = si;i+m 1 or not is determined by mrp( i) 2 Des(CS (P)). If LCA(mrp( i ); CS (P)) = CS (P), then mrp( i) 2 Des(CS (P)) holds. By Lemma 4, the query LCA(mrp( i ); CS (P)) can be answered in O(1) time after an O(nN ) time and space preprocessing of MTPH (T). Thus, the comparison of CS (P) with si;i+m 1 can be done in O(1) time. Hence, the total time is O(mN + occ) in this case, di erent from O(m2N + occ) time of the naive algorithm. Remark that, unfortunately, this result does not improve the upperbound of the time complexity of the matching for the worst case. If CS (P) is not represented in MTPH (T), we must compute CS (P) = si;i+m 1, that takes O(mN ) time. In this case, all comparisons are done in O(m2N ) time because jIj < m. By considering the above two cases, the time bound of the matching is O(mN + occ + m2N ) = O(m2N + occ).
Theorem 2. Problem 1 can be solved in O(m2N +occ) time by using MTPH (T) with MRPs. 4
We propose a more space-e cient version of MTPH, by omitting non-indexing nodes of MTPH (see Figure 1, right).
De nition 5 (CMPTH). Let T be a multi-track string of length n and track count N over . Let S = fs1; s2; : : : ; sng be an ordered set of strings, where si = CS (T[i:]) for 1 i n. A contracted multi-track position heap of T, denoted by CMTPH (T), is a sequence hash tree of S, i.e., CMTPH (T) = SHT (S). Since CMTPH (T) is a sequence hash tree for an ordered set of cardinality n, it has n + 1 nodes and n edges, so that CMTPH (T) consumes only O(n) space.
compute SI (T[i :]) for 1 i n in O(nN ) time, then insert all si = CS (T[i:]) to the tree in order; each insertion can be done in O(n), so that O(n2) in total.
We now show a more e cient construction algorithm for CMTPH (T), that runs in O(nN ) time. It re-assign the positions in the nodes in MTPH (T), and eliminates all non-indexing nodes as follows. First let us noticed that in Figure 1, CMTPH (T) is a subtree of MTPH (T) with the same root node, if we ignore the positions stored in the nodes. It is always the cases, as follows.
Lemma 8. For 1 i n, CMTPH i(T) is a subtree of MTPH i(T) rooted by the root of MTPH i(T), if we ignore the positions stored in the nodes. Proof. CMTPH i(T) is a sequence hash tree of S = fs1; s2; : : : ; sig. On the other hand, MTPH i(T) is equivalent to a sequence hash tree of S0 = Sik=1 Sj=k1 fskg = fs1; : : : ; s1; s2; : : : ; s2; : : : ; si; : : : ; sig. Because S is a subset of S0, the statement | {z1 } | {z2 } | {zi } holds by Lemma 1. tu
Lemma 8 implies that all nodes and edges in CMTPH (T) are included in MTPH (T). Therefore, CMTPH (T) can be obtained by the following process. For each i = 1; 2; : : : ; n, we re-assign the position i stored in an indexing node i to its ancestor node i 2 Anc( i), that does not store the primary position (i.e., i may store the secondary position) and the farthest from i (i.e., nearest from the root ). If there is no such a node, then i keeps storing i. After that, we eliminate all nodes that stores no position. Then, the remaining tree is CMTPH (T).
To nd i e ciently, we use the two types of queries on a rooted tree, that are the nearest marked ancestor query and the level ancestor query referred in Lemma 3 and Lemma 4, respectively. Each query can be answered in constant time after a linear-time preprocess of the tree.
We now show how to nd i from i. We mark a node to indicate that the node stores some positions in CMTPH (T). At the beginning, only the root of MTPH (T) is marked. Because i is the farthest unmarked ancestor of i, it is the depth d + 1 ancestor of i, where d is the depth of the nearest marked ancestor u of i. The ancestor u is obtained by NMA( i ), and then i by LevA(u; depth(u) + 1 ), both in O(1) time. If u 6= i, re-assign the position i from i to i, and mark i. Otherwise, i.e., u = i, do nothing. Repeating it for i = 1; 2; : : : ; n, we get CMTPH (T) in O(n) time from MTPH (T). Because MTPH (T) can be constructed in O(nN ) time, we obtain the following result. Theorem 3. Given a multi-track T of length n and track count N , CMTPH (T) can be constructed in O(nN ) time and space.
CMTPHs is useful for permuted pattern matching instead of MTPHs. Because any node in CMTPH stores at least one position, the candidate positions for matching is at most jIj = O(mN ). Thus, the time complexity is
O(m2N 2 + occ). It can be improved by using the maximal-reach pointers for CMTPH, denoted by cmrp( i), in the same way as MTPH. Because cmrp( i) = NMA(mrp( i )) holds for any i after marking all i's, we get them in O(n) time. Thus we have the following results.
Theorem 4. Given a multi-track T of length n and track count N , CMTPH (T) with the maximal-reach pointers for CMTPH (T) can be constructed in O(nN ) time and space.
For the permuted pattern matching, the maximal-reach pointers of CMTPH work similarly to that of MTPH. Thus, it is not di cult to see that the following theorem holds.
Theorem 5. Problem 1 can be solved in O(m2N 2 + occ) time by using CMTPH (T) with the maximal-reach pointers. 5
We proposed two new indexing structures, MTPH and CMTPH, for multi-track
strings, that are memory-e cient compared with the multi-track su x tree in
[