Computing longest common square subsequences

Computing longest common square subsequences Takafumi Inoue Department of Informatics, Kyushu University, Japan Shunsuke Inenaga Department of Informatics, Kyushu University, Japan [email protected]u-u.ac.jp Heikki Hyyrö Faculty of Natural Sciences, University of Tampere, Finland heikki.h[email protected] Hideo Bannai Department of Informatics, Kyushu University, Japan [email protected]u-u.ac.jp https://orcid.org/0000-0002-6856-5185 Masayuki Takeda Department of Informatics, Kyushu University, Japan tak[email protected]u-u.ac.jp Abstract Asquare is a non-empty string of form Y Y . The longest common square subsequence (LCSqS) problem is to compute a longest square occurring as a subsequence in two given strings Aand B. We show that the problem can easily be solved in O(n6)time or O(|M|n4)time with O(n4) space, where nis the length of the strings and Mis the set of matching points between Aand B. Then, we show that the problem can also be solved in O(σ|M|3+n)time and O(|M|2+n) space, or in O(|M|3log2nlog log n+n)time with O(|M|3+n)space, where σis the number of distinct characters occurring in Aand B. We also study lower bounds for the LCSqS problem for two or more strings. 2012 ACM Subject Classification Mathematics of computing →Combinatorial algorithms Keywords and phrases squares, subsequences, matching rectangles, dynamic programming Digital Object Identifier 10.4230/LIPIcs.CPM.2018.15 Acknowledgements The authors thank the anonymous referees for correcting errors involved in an earlier version of this paper. 1 Introduction Computing the longest common subsequence (LCS) of given strings is the fundamental way to compare the strings. Given two strings A and B of length n each, the basic dynamic programming solution computes the LCS of A and B in O ( n2 )time and space [ 27 ]. While faster solutions for the LCS problem exist, such as those running in O ( n2/log2n )time for constant-size alphabets [ 22 ], and in O ( n2 ( log log n ) 2/log2n )time or in O ( n2log log n/ log2n ) time for non constant-size alphabets [ 5 , 12 ] 1 , no strongly sub-quadratic O ( n2− )-time 1 Grabowski’s method [ 12 ] works when the length m of one string is at least log2n , where n is the length of the other string. ©Takafumi Inoue, Shunsuke Inenaga, Heikki Hyyrö, Hideo Bannai, and Masayuki Takeda; licensed under Creative Commons License CC-BY 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Editors: Gonzalo Navarro, David Sankoff, and Binhai Zhu; Article No. 15; pp. 15:1–15:13 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany Published in 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) pp. 15:1--15:13. Eds. by Navarro G., Sankoff D. & Zhu B. Dagstuhl: Schloss Dagstuhl. ISBN: 978-3-95977-074-3. http://dx.doi.org/10.4230/LIPIcs.CPM.2018.15 15:2 Computing longest common square subsequences solutions are known for any constant  > 0. Difficulty in breaking this barrier is supported by recent studies on conditional lower bounds for string similarity measures: It is shown in [ 1 ] that if there is an O ( n2− )-time solution for the LCS problem with a constant  > 0, then the famous strong exponential time hypothesis (SETH ) fails. To reflect a priori knowledge to the solution to be found, many variants of the LCS problem where some constraints are introduced in the solution have been considered (see e.g. [7, 2, 14, 20, 9, 10, 28, 11, 29, 30, 8, 16, 19]). This paper considers a new variant of the LCS problem where the solution must be a square (of form Y Y with some string Y ), called the longest common square subsequence (LCSqS) problem defined as follows: Given two strings A and B of length n , compute (the length of) a longest square which appears as a subsequence in A and B . For instance, for A = babcabdbaca and B = dbcacbbcacd , their LCSqSs are bacbac and bcabca of length 6. We propose several solutions for the LCSqS problem. We first show that there is a simple O ( n6 )-time O ( n4 )-space solution for the LCSqS problem. The algorithm is also improved to O ( |M|n4 )-time by using the set M of matching points between the two input strings. Albeit M can be as large as O ( n2 )in the worst case, it can be smaller in many cases. We then give two more sophisticated algorithms based on the set R of matching rectangles: one runs in O ( σ|M||R| + n ) = O ( σ|M|3 + n )time with O ( |M|2 + n )space, and the other in O ( |M||R| log2log log n + |M|3 + n ) = O ( |M|3log2log log n + n )time with O ( |M|3 + n )space, where σ denotes the number of distinct characters that appear in both strings. These two solutions are faster than the simple O ( n6 )-time or O ( |M|n4 )-time solutions when M is sparse. Note e.g. that under uniformly distributed random text |M| ≈ n2/σ and |R| ≈ |M|2/σ ≈n4/σ3 , in which case the expected running times of our three algorithms would be O(n6/σ),O(n6/σ3)and O(n6(log2log log n+σ)/σ4)respectively. The set M of matching points can easily be computed in O ( |M| + n )time under a common assumption that the input strings are over an integer alphabet of size nO(1). We also study hardness of the LCSqS problem for two or more strings. The k -LCSqS problem is to compute the LCSqS of given k≥ 2strings. We show that the k -LCSqS problem is at least as hard as the 2 k -LCS problem which asks to compute the LCS of 2 k given strings. This implies that for unfixed k the k -LCSqS problem is NP-hard, and that for fixed k it seems hard to solve the k-LCSqS problem in O(nk−)time for any constant  > 0. Related work It is known that one can compute (the length of) a longest square subsequence (LSqS) of a single string of length n in O ( n2 )time and O ( n )space [ 18 ]. Also, it is shown in [ 1 ] that if there is an O ( n2− )-time solution for the LSqS problem with a constant  > 0, then the famous strong exponential time hypothesis (SETH ) fails. Our results for the LCSqS problem can be seen as a generalization of these results for the LSqS problem. Technically speaking, our results for the LCSqS problem are most related to those for the longest common palindromic subsequence (LCPS) problem, where the task is to find a longest palindrome that appears as a subsequence in both of the two strings A and B . Chowdhury et al. [ 8 ] were the first to consider the LCPS problem, giving an O ( n4 )-time solution and an O ( |M|2log2nlog log n + n )-time solution 2 . Inenaga and Hyyrö [ 16 ] proposed another 2 Our careful analysis reveals that Chowdhury et al.’s algorithm [ 8 ] uses at least Ω( min{|M|2n2log n, n3} ) space (and hence time), but it can be fixed to run in O ( |M|2log2nlog log n + n )time using our technique proposed in Section 3. T. Inoue, S. Inenaga, H. Hyyrö, H. Bannai, and M. Takeda 15:3 algorithm which solves the LCPS problem in O ( σ|M|2 + n )time and O ( |M|2 + n )space. Very recently, Bae and Lee [ 3 ] showed how to solve the LCPS problem in O ( |M|2 + n )time. Inenaga and Hyyrö [ 16 ] also showed that the LCPS problem for two strings is at least as hard as the LCS problem for four strings, implying that it seems hard to solve the LCPS problem in O(n4−)time for any constant  > 0. 2 Preliminaries Let Σbe the alphabet. An element X of Σ ∗ is called a string. The length of string X is denoted by |X| . For any 1 ≤i≤ |X| , X [ i ]denotes the i th character of X . For any 1 ≤i≤j≤ |X| , X [ i..j ]denotes the substring of X beginning at position i and ending at position j. A string X is said to be a subsequence of another string Y if there exists a sequence 1 ≤i1<· · · < i|X|≤ |Y| of increasing positions of Y such that X = Y [ i1 ] · · · Y [ i|X| ]. In other words, a subsequence of Y can be obtained by removing zero or more characters from Y . The k -LCS problem is to compute the length of a longest common subsequence (LCS) of given k strings, where k≥ 2. Let LCS ( A1, . . . , Ak )denote the length of a longest common subsequence of k strings A1, . . . , Ak . A non-empty string X of length 2 k is called asquare if there exists a string Y of length k such that X = Y Y . A square S is called a square subsequence of another string Y if square S is a subsequence of Y . Let LCSqS ( A, B ) denote the length of a longest common square subsequence (LCSqS) of strings A and B . This paper deals with the problem of computing LCSqS ( A, B )for two given strings A and B . For simplicity, we assume that the input strings A and B are of the same length and let n = |A| = |B| . Our algorithms can easily be extended to the case where |A| 6 = |B| as well as to the case where we wish to compute one longest common square subsequence of A and B . For two strings A and B , a pair ( i, j )of positions 1 ≤i≤ |A| and 1 ≤j≤ |B| is said to be a matching point if A [ i ] = B [ j ]. The set of all matching positions of A and B is denoted by M ( A, B ), namely, M ( A, B ) = { ( i, j ) | 1 ≤i≤ |A|, 1 ≤j≤ |B|, A [ i ] = B [ j ] } . We will abbreviate M(A, B)as Mwhen it is clear from the context. 3 Algorithms In this section, we present several algorithms for computing LCSqS ( A, B ). In order to avoid processing unnecessary characters, we will assume that the input strings A and B have been already preprocessed by an alphabet reduction technique [ 16 ] as follows: First, we compute the lexicographical ranks of the characters in A and B . Assuming that A and B are drawn from an integer alphabet of size nO(1) , this can be done in O ( n )time with radix sort. We then replace each character in A and B with its rank, turning A and B into strings over the integer alphabet [1 , 2 n ]. Then we remove every character that appears only either in A or in B . It is clear that this preprocessing essentially preserves common subsequences between the original A and B and thus has no negative effect on computing LCSqS ( A, B ). Note that n≤ M holds after alphabet reduction, while M=O(n2)still also holds. 3.1 Simple Algorithm Our first algorithm considers Θ( n2 )pairs of partitioning of A and B . Namely, we have that LCSqS(A, B) = max 1≤i<n,1≤j<n{2×LCS(A[1..i], A[i+ 1..n], B[1..j], B[j+ 1..n])}. CPM 2018 15:4 Computing longest common square subsequences This immediately implies an O ( n6 )-time O ( n4 )-space algorithm for computing LCSqS ( A, B ), since the LCS of four strings can be computed in O(n4)time and space by standard DP. The O ( n6 )-time complexity can be improved as follows. For any matching point ( i, j ) ∈ M , let i0 (resp. j0 ) be the smallest position such that i < i0 , j < j0 , and ( i0, j0 ) ∈ M . If such (i0, j0)does not exist, then let i0=j0=n. IObservation 1. For any i≤k < i0 and j≤h<j0 , LCS ( A [1 ..k ] , A [ k + 1 ..n ] , B [1 ..h ] , B [ h + 1..n] = LCS(A[1..i], A[i+ 1..n], B[1..j], B[j+ 1..n]. By Observation 1, it is sufficient for us to consider only |M| partition points between A and B. Hence, we can compute LCSqS(A, B)in O(|M|n4)time and O(n4)space. 3.2 O(σ|M|3+n)-time algorithm Here we present our O ( σ|M|3 + n )-time algorithm for computing LCSqS ( A, B ), where σ is the number of distinct characters occurring in A and B . This algorithm is based on Inenaga and Hyyrö’s algorithm [ 16 ] which computes (the length of) a longest palindromic common subsequence of two given strings in O ( σ|M|2 + n )time. Consider a 2D plain where the string A corresponds to the vertical axis upward (i.e., A [1] is on the bottom and A [ n ]is on the top), and the string B corresponds to the horizontal axis rightward (i.e., B [1] is on the left end and B [ n ]is on the right end). Our key idea is to represent each common square subsequence of strings A and B by matching rectangles defined as follows: For 1 ≤i < j ≤n and 1 ≤k < l ≤n , a tuple r = ( i, j, k, l )is said to be a matching rectangle iff A [ i ] = A [ j ] = B [ k ] = B [ l ], and more specifically a c -matching rectangle iff A [ i ] = A [ j ] = B [ k ] = B [ l ] = c . For a matching rectangle r = ( i, j, k, l ),( i, k )is said to be the left-bottom corner of r , and ( j, l )is said to be the right-upper corner of r . Let R denote the set of matching rectangles of A and B . Notice |R| = O ( |M|2 ). For two matching rectangles r= (i, j, k, l)and r0= (i0, j0, k0, l0), let r=r0⇐⇒ i=i0, j =j0, k =k0,and l=l0 r < r0⇐⇒ i<i0, j < j0, k < k0,and l < l0 rCr0⇐⇒ i≤i0, j ≤j0, k ≤k0, l ≤l0,and r6=r0. For two c-matching rectangles r= (i, j, k, l)and r0= (i0, j0, k0, l0), let rr0⇐⇒ i≤i0, j ≤j0, k ≤k0and l≤l0. A sequence hr1, . . . , rmi of matching rectangles is said to be a sequence of diagonally overlapping matching rectangles (DOMRs) iff rx< rx+1 for all 1 ≤x<m , im< j1 and km< l1 , where we use the notation rh = ( ih, jh, kh, lh )for all h = 1 , . . . , m . The size of a sequence hr1, . . . , rmiof DOMRs is the number mof overlapping rectangles in it. The following observation lays the foundation to the algorithms of this subsection (and to the one of the following subsection as well): IObservation 2. There is a common square subsequence T of length 2 m of strings A and Biff there exists a sequence hr1, . . . , rmiof DOMRs of length m. See Figure 1 which depicts the relationship between common square subsequences and DOMRs for two strings A and B . By Observation 2, the problem of computing LCSqS ( A, B ) reduces to the problem of finding a longest sequence of DOMRs. T. Inoue, S. Inenaga, H. Hyyrö, H. Bannai, and M. Takeda 15:5 … a … b … c … a … b … c … ! A ! B ! c b a c b a! …!…!…!…!…!…!…! Figure 1 Illustration of the relationship between common square subsequences and DOMRs. The basic idea of our algorithm is to extend a given sequence S = hr1, . . . , rmi of DOMRs by adding a new matching rectangle to its right-end. We say that a c -matching rectangle r = ( i, j, k, l )is a c -extension of S if hr1, . . . , rm, ri is a sequence of DOMRs. A c -extension r of S is dominant if the condition rr0 holds between r and any c -extension r0 of S . The algorithms in this subsection are based on the following lemmas. ILemma 3. Let S = hr1, . . . , rmi be any sequence of DOMRs. If S has at least one c - extension, then S has a unique dominant c -extension r0 . It is furthermore possible to compute any such r0in O(1) time after initial preprocessing of Aand Bin O(σn)time and space. Proof. Consider r0 = ( i0, j0, k0, l0 ), where i0 = min ( {i|im<i<j1, A [ i ] = c}∪{n + 1 } ), j0 = min ( {j|jm< j, A [ j ] = c} ∪ {n + 1 } ), k0 = min ( {k|km< k < l1, B [ k ] = c} ∪ {n + 1 } ) and l0 = min ( {l|l > lm, B [ l ] = c}∪{n +1 } ). If any of i0 , j0 , k0 and l0 holds the sentinel value n + 1 that corresponds to non-existence of a further suitable match with c , then S cannot have any c -extension. Otherwise A [ i0 ] = A [ j0 ] = B [ k0 ] = B [ l0 ] = c and r0 is a c -matching rectangle. Furthermore im< i0 , jm< j0 , km< k0 , lm< l0 , i0< j1 and k0< l1 , so r0 is a c -extension of S . If we assume the existence of another c -extension r0 of S such that r00 r0 does not hold, then at least one of the definitions of i0 , j0 , k0 and l0 above is contradicted. Hence r0 must be dominant. Finally, r0 must clearly be unique: if also r00 6 = r0 is a dominant c-extension, then both r0r00 and r00 r0must hold, but this is possible only if r00 =r0. The values i0 and j0 can be computed in O (1) time by using a precomputed table PA of size σ×n that holds the values PA [ c, h ] = min ( {i|h < i, A [ h ] = c} ∪ {n + 1 } )for all c∈ Σ and 1 ≤h≤n . The values k0 and l0 can be computed in O (1) time by using an analogous precomputed table PB with values PB [ c, h ] = min ( {i|h < i, B [ h ] = c}∪{n + 1 } ). Both tables can be precomputed in O(σn)time and space in a straight-forward manner. J Note that the proof of Lemma 3 refers only to r1 and rm when determining the unique dominant extension of hr1, . . . , rmi : any inner rectangle ri for 1 < i < m does not need to be considered. Thus all sequences of DOMRs that begin with the rectangle r1 and end with the rectangle rmshare the same unique dominant extensions. ILemma 4. Let S = hr1, . . . , rmi be any sequence of at least two DOMRs. If any c -matching rectangle rh with 1 < h ≤m is replaced by the dominant c -extension of hr1, . . . , rh−1i , also the resulting sequence of matching rectangles is a sequence of DOMRs. Proof. The lemma clearly holds if h = m , so consider the case 1 <h<m . Let ( i0, j0, k0, l0 ) be the dominant c -extension of hr1, . . . , rh−1i , and let S0 = hr0 1, . . . , r0 mi denote the sequence obtained from S by replacing rh with ( i0, j0, k0, l0 ). S is a sequence of DOMRs, and thus CPM 2018 15:6 Computing longest common square subsequences i0 m = im< j1 = j0 1 , k0 m = km< l1 = l0 1 , and rx< rx+1 for 1 ≤x<m . On the other hand r0 h−1< r0 h , as also hr0 1, . . . , r0 hi = hr1, . . . , rh−1, ( i0, j0, k0, l0 ) i is a sequence of DOMRs. Because r0 h is dominant, we have r0 h−1< r0 hrh< rh+1 = r0 h+1 , which in turn implies that r0 h< r0 h+1 for 1≤h<m, and hence S0fulfills all conditions of a sequence of DOMRs. J Basic algorithm. The basic principle of our first rectangle-based algorithm, Algorithm 1, is to fix the first left-bottom matching rectangle rb , and then try to extend it as long as possible to the right-upper direction. For each such starting rectangle rb , we compute a dynamic programming table DPrb of size O ( |M|2 )such that DPrb [ re ]will finally store the length of the longest sequence of DOMRs beginning with rb and ending with re , where re is either rbitself or a dominant extension. In more detail, Algorithm 1 works as follows: Algorithm 1: Preprocessing: Compute a list L of all matching rectangles sorted according to < and by radix sorting all rectangles (i, j, k, l)as 4-digit numbers. Compute longest sequence of DOMRs: For each matching rectangle rb (in any order), perform the following: (1) For each re(6=rb), we initialize DPrb[re]←0. We let DPrb[rb]←2. (2) Suppose rb is the i th element of L . For each j = i + 1 ,...,|L| in increasing order, let r←L[j]and attempt to extend a sequence hrb, . . . , riof DOMRs as follows: (a) If DPrb[r]=0, then no sequence of DOMRs of form hrb, . . . , riexists. (b) Otherwise, for each character c , try to compute the unique dominant c -extension r0 of any sequence hrb, . . . , ri of DOMRs which begins with rb and ends with r . If such r0exists, set DPrb[r0]←max{DPrb[r0], DPrb[r]+2}. (3) If the maximum value in DPrbexceeds the current best solution, then update it. Let us explain the correctness of Algorithm 1. Lemma 4 guarantees that an optimal sequence of DOMRs can be constructed by considering only dominant extensions. Consider any such optimal sequence of DOMRs S = hr1, . . . , rmi . The outer loop of Algorithm 1 will at some point select rb = r1 . As r←L [ j ]are processed in increasing order of j , the sorting order of L guarantees that rectangles ri of S will be selected as the current r in the order i = 1 , . . . , m . For each such r = ri , the algorithm uses Lemma 3 to consider all possible dominant extensions, including also the extension ri+1 if i<m . A simple inductive argument shows that the values DPr1[ri]will become correctly computed in the order i= 1, . . . , m. Let us analyze the efficiency of Algorithm 1. Constructing the tables PA and PB takes O ( σn )time and space. Note that alphabet reduction guarantees that O ( σn ) = O ( σ|M| ). Since 1 ≤i, j, k, l ≤n for each matching rectangle ( i, j, k, l ), we obtain a sorted list L of all O ( |M|2 )matching rectangles in O ( |M|2 + n )time and space by radix sort. Hence the preprocessing takes O ( |M|2 + n )total time and space. We test no more than σ characters for any cell DPrb [ r ]of the dynamic programming table DPrb . By Lemma 3, we can compute a unique dominant c -extension in O (1) time, if it exists. Since there are O ( |M|2 )candidates for rb and O ( |R| ) = O ( |M|2 )candidates for r , Algorithm 1 takes overall O ( σ|M|4 + n )time and O(|M|2+n)space. Improved algorithm. Now we show how to reduce the number of candidates for the starting rectangle rb. We give proof for Lemma 5. Lemmas 6 and 7 can be proven similarly. T. Inoue, S. Inenaga, H. Hyyrö, H. Bannai, and M. Takeda 15:7 ILemma 5. Let rb1 = ( ib1, jb1, kb1, lb1 )and rb2 = ( ib2, jb2, kb2, lb2 )be any matching rectangles s.t. ib1< ib2 , jb1 = jb2 , kb1 = kb2 , and lb1 = lb2 . Let `1 and `2 be the lengths of LCSqS of A and B whose corresponding sequences of DOMRs begin with rb1 and rb2 , respectively. Then, `1≥`2. Proof. See Figure 2 for illustration. It follows from jb1 = jb2 , kb1 = kb2 , and lb1 = lb2 that the two matching rectangles rb1 and rb2 correspond to the same character. Let hrb2,1, rb2,2, . . . , rb2,`2i be any sequence of DOMRs which begins with rb2 and represents a common square subsequence of length `2 , namely rb2 = rb2,1 . Since ib1< ib2 , jb1 = jb2 , kb1 = kb2 , and lb1 = lb2 , hrb1, rb2,2, . . . , rb2,`2i is a sequence of DOMRs which begins with rb1 and represents a common square subsequence of length `2. This implies that `1≥`2.J ILemma 6. Let rb1 = ( ib1, jb1, kb1, lb1 )and rb2 = ( ib2, jb2, kb2, lb2 )be any matching rectangles s.t. ib1 = ib2 , jb1 = jb2 , kb1< kb2 , and lb1 = lb2 . Let `1 and `2 be the lengths of LCSqS of A and B whose corresponding sequences of DOMRs begin with rb1 and rb2 , respectively. Then, `1≥`2. ILemma 7. Let rb1 = ( ib1, jb1, kb1, lb1 )and rb2 = ( ib2, jb2, kb2, lb2 )be any matching rectangles such that ib1< ib2 , jb1 = jb2 , kb1< kb2 , and lb1 = lb2 . Let `1 and `2 be the lengths of longest common square subsequences of A and B whose corresponding sequences of DOMRs begin with rb1and rb2, respectively. Then, `1≥`2. It follows from Lemmas 5–7 that it suffices to consider only all right-upper corners ( jb, lb ) instead of all matching rectangles rb = ( ib, jb, kb, lb ). Namely, for each arbitrarily fixed right-upper corner ( jb, lb )such that A [ jb ] = B [ lb ] = c , we can always use ( imin, kmin )as its left-bottom corner, where imin and kmin are respectively the left-most occurrences of character cin Aand B. The following is our improved algorithm. Algorithm 2: Preprocessing: As in Algorithm 1, but now also precompute positions ib = min{i| A[i] = c}and kb= min{k|B[k] = c}for each character cthat appears in Aand B. Computing longest sequence of DOMRs: For each matching point pb = ( jb, lb ) ∈ Mwe perform the following: (i) Let c = A [ jb ] = B [ lb ]. We compute ib = min{i|A [ i ] = c} and kb = min{k|B [ k ] = c} , and let rb← ( ib, jb, kb, lb ). If ib = jb or kb = lb , then we stop processing the current matching point and proceed to the next matching point in M. (ii) Perform the same procedures (1)–(3) as in Algorithm 1. (iii) If the maximum value in DPrbexceeds the current best solution, then update it. The correctness of Algorithm 2 follows from that of Algorithm 1 and Lemmas 5-7. Let us analyze the efficiency of Algorithm 2. For all characters c , we can precompute ib = min{i|A [ i ] = c} and kb = min{k|B [ k ] = c} in total O ( n )time and space. The other preprocessing steps are the same as in Algorithm 1 and take O ( σ|M| + n )total time and space. There are O ( |M| )candidates for the right-upper corner pb = ( jb, lb )of the first matching rectangle from which considered sequences of DOMRs begin. For each pb = ( jb, lb ), its left-bottom corner ( ib, kb )can be retrieved in O (1) time. We again test no more than σ characters for any cell DPrb [ r ], and Lemma 3 allows to check each unique dominant c -extension in O (1) time. Since there are O ( |M| )candidates for rb and O ( |R| ) = O ( |M|2 ) CPM 2018 15:8 Computing longest common square subsequences … a … a … ! a a a! ib1! ib2! jb1! jb2 =! kb1!lb1! kb2!lb2! =! =! …!…!…!…! A ! B ! Figure 2 Illustration for Lemma 5. … a … a … a … ! a a ib1! ib2 =! jb1! jb2 =! kb1!lb1! kb2!lb2! =! …!…!…! A ! B ! Figure 3 Illustration for Lemma 6. … a … a … a … ! a a a! ib1! ib2! jb1! jb2 =! kb1!lb1! kb2!lb2! =! …!…!…!…! A ! B ! Figure 4 Illustration for Lemma 7. candidates for r , the whole algorithm takes overall O ( σ|M|3 + n )time and O ( |M|2 + n ) space. We have shown the following theorem: ITheorem 8. We can compute LCSqS ( A, B )in O ( σ|M|3 + n )time and O ( |M|2 + n )space. 3.3 O(|M|3log2nlog log n+n)-time algorithm In this section we propose an O ( |M|3log2nlog log n + n )-time and O ( |M|3 + n )-space algorithm for computing LCSqS(A, B). For any 1 ≤i<s≤j≤n and 1 ≤k < t ≤l≤n , let LCSqSs,t ( i, j, k, l ) = 2 × LCS(A[1..i], A[s..j], B[1..k], B[t..l]). By definition, LCSqS(A, B) = max1≤i<s≤j≤n,1≤k<t≤l≤n,(s,t)∈M{LCSqSs,t(i, j, k, l)}. Now, let ( s, t ) ∈ M be an arbitrarily fixed matching point between A and B . This corresponds to Observation 1. A recurrence for computing LCSqSs,t ( i, j, k, l )is given as follows: LCSqSs,t(i, j, k, l) =                            max(i0,j0,k0,l0)<(i,j,k,l){LCSqSs,t(i0, j0, k0, l0)}+ 2 ((i, j, k, l)∈ R, 1≤i<s≤j≤n, 1≤k < t ≤l≤n) max(i0,j0,k0,l0)C(i,j,k,l){LCSqSs,t(i0, j0, k0, l0)} ((i, j, k, l)/∈ R, 1≤i<s≤j≤n, 1≤k < t ≤l≤n) 0(otherwise) (1) Our technique for computing LCSqSs,t ( i, j, k, l )is similar to Chowdhury et al.’s method [ 8 ] for computing longest common palindromic subsequences, which uses the following wellknown van Emde Boas tree data structure: Let S be a set of integers from the universe [1 , U ]. The van Emde Boas tree for S takes Θ( U )space and supports predecessor/successor queries and insertion/deletion operations on Sin O(log log U)time each [26]. Let ( s, t ) ∈ M be an arbitrary fixed matching point. We plot a point ( i, j, k )on the 3D grid [1 ..n ] × [1 ..n ] × [1 ..n ]if and only if there is a matching rectangle of form ( i, j, k, ∗ ), namely, one having i, j, k as its first three coordinates. This 3D point ( i, j, k )will finally be associated with max(i,j,k,l)∈R{LCSqSs,t(i, j, k, l)}. T. Inoue, S. Inenaga, H. Hyyrö, H. Bannai, and M. Takeda 15:9 Now we show how to compute those associated values for all the 3D points. We consider the permuted tuples ( l, i, j, k )and sort them as 4-digit numbers, like we did for L in Section 3.2. We process the permuted tuples in this sorted order. Suppose we are to process a permuted tuple ( l, i, j, k )such that its original tuple ( i, j, k, l )is in R . It is now guaranteed that we have processed all tuples ( l0,∗,∗,∗ )with l0< l . Therefore, if z is the maxima among the associated values of all 3D points in the range [1 ..i − 1] × [1 ..j − 1] × [1 ..k − 1], then we have that LCSqSs,t ( i, j, k, l ) = z + 2 (see also the recurrence (1) above). We maintain these 3D points with a variant of the 3D range tree [ 4 ]. Then, the maxima z can be efficiently retrieved by querying the point with the maximum associated value in the range [1 ..i − 1] × [1 ..j − 1] × [1 ..k − 1]. If there is no existing 3D point ( i, j, k ), then we insert this point with the associated value z + 2. Otherwise, we update the associated value of the already existing 3D point (i, j, k)with z+ 2. The 3D range tree is a three layered data structure: The top layer tree maintains the first i -coordinate [1 ..n ], and each of its nodes is associated with a middle layer tree. Each middle layer tree maintains the second j -coordinate [1 ..n ], and each of its nodes is associated with a bottom layer tree. Each bottom layer tree maintains the third k -coordinate [1 ..n ]. Since each bottom layer tree can contain O ( n )nodes, each middle layer tree can contain at most O ( n )nodes, and the top layer can contain at most O ( n )nodes, the total size of the 3D range tree data structure is trivially bounded by O ( n3 ) = O ( |M|3 ). Since at most O ( |M|2 ) points are inserted to the 3D range tree and since |M| = O ( n2 ), the 3D range tree supports range maxima queries and insertions of new points in O(log3(|M|2)) = O(log3n)time. Next, we improve the query and update times from O ( log3n )to O ( log2nlog log n ). Chowdhury et al. [ 8 ] claimed that using the technique from [ 15 ] it is possible to replace each 1D range tree on the bottom layer with a van Emde Boas tree data structure [ 26 ], leading to O ( log2nlog log n )query and update times. However, the way how van Emde Boas trees are used in the approach of [ 15 ] indeed requires to maintain a set of integers in the universe of size Θ( n2 ). This implies that each van Emde Boas tree requires Θ( n2 )space. Since the total size of the top layer tree and the middle layer trees is O ( n2 ), and since each node of a middle layer tree maintains a van Emde Boas tree of size O ( n2 ), it takes O ( n4 )space 3 . This is, however, prohibitive since it can exceed our target time bound O ( |M|3log2nlog log n ) when the set M of matching points is sparse (e.g., when |M| = Θ( n )). Below, we will reduce the space requirement for the van Emde Boas trees used in our data structure. Space efficient 3D range tree with van Emde Boas trees. We briefly recall how the algorithm of [ 15 ] computes the maxima in a given range using a van Emde Boas tree. Let D [1 ..n ]be an array of monotonically non-decreasing non-negative integers from [0 ..n ], namely, 0 ≤D [ k ] ≤n for all 1 ≤k≤n and D [ k ] ≤D [ k + 1] for all 1 ≤k < n . We will store in D the associated values of 3D points in increasing order of positions, and in the sequel we assume that D [ k + 1] −D [ k ] ∈ { 0 , 2 } . Let RMQS (1 , k )denote a query to return the maxima in the sub-array D [1 ..k ]for 1 ≤k≤n . For any integer val (1 ≤val ≤n ), if some entry of D stores val , then we insert the pair ( pos,val )s.t. pos is the rightmost position in D that stores val . For instance, if D = [0 , 0 , 2 , 4 , 4 , 6], then the van Emde Boas tree maintains the set { (2 , 0) , (3 , 2) , (5 , 4) , (6 , 6) } of integer pairs. However, since a van Emde Boas tree is an integer data structure, we convert each pair ( pos,val )to integer pos × ( n + 1) + val and insert 3 A more careful analysis reveals that the total size of this variant of the 3D range tree with van Emde Boas bottom layer trees is O ( |M|2n2log n ), however, this can also exceed O ( |M|3log2nlog log n )when Mis sparse. CPM 2018