CPM 2018

Computing longest common
square subsequences
Takafumi Inoue1, Shunsuke Inenaga1,Heikki Hyyrö2, Hideo Bannai1, Masayuki Takeda1
1Kyushu University

2University of Tampere

Longest Common Subsequence (LCS)LCS Problem
Input: two strings A and B of length n each
Output: (length of) LCS of A and B
LCS is a classical measure for string comparison.
 Standard DP solves this in O(n2) time.
E.g.) A = aacaabadvsB = cacbcbbd

Longest Common Subsequence (LCS)LCS Problem
Input: two strings A and B of length n each
Output: (length of) LCS of A and B
LCS is a classical measure for string comparison.
 Standard DP solves this in O(n2) time.
E.g.) A = aacaabad
vsB = cacbcbbd

Constrained/Restricted LCS
 Variants of LCS problem where the solution

must satisfy pre-determined constraints.

 Attempt to reflect user’s a-priori knowledge

to the solutions.



STR-IC-LCS, STR-EC-LCS, SEQ-IC-LCS, SEQ-EC-LCS
LCS of A and B that includes (excludes)
given pattern P as a substring (subsequence).
(See [Kuboi et al, CPM 2017] and references therein)Longest common palindromic subsequence (LCPS)[Chowdhury et al. 2014, Inenaga & Hyyrö 2018, Bae & Lee 2018]

Longest Common Square Subseq. (LCSS)
 This work considers new variant of LCS,

called LCSS, where the solution has to be square.

 Square (a.k.a. tandem repeat) is string of form xx.
aabaababababab

abcbbabcbb

Longest Common Square Subseq. (LCSS)LCSS Problem
Input: two strings A and B of length n each
Output: (length of) LCSS of A and BE.g.)
A = monsterstrikevsB = fourstringmasters

Longest Common Square Subseq. (LCSS)LCSS Problem
Input: two strings A and B of length n each
Output: (length of) LCSS of A and BE.g.)
A = monsterstrike

vsB = fourstringmasters

Our Results
Upper bounds (algorithms) for LCSS
algorithm

timespace

Naïve

O(n6)

O(n4)

SimpleO(M n4)O(n4)Matching rectangle 1O(σM 3 +n)O(M 2 +n)

Matching rectangle 2O(M 3 log2n loglog n + n)O(M 3 +n)n is the length of the input strings.
 M is the number of matching points,i.e., M = |{(i, j) | A[i] = B[j], 1 ≤ i, j ≤ n}|.
 σ is the alphabet size.
Matching Points

M is the number of matching points,i.e., M = |{(i, j) | A[i] = B[j], 1 ≤ i, j ≤ n}|.
a ●
b

A

●
● ●a ●

●
●

●

●

b

● ●

●

b

● ●

●

a ●

●

●

a b b a b a

BMatching Points

M is the number of matching points,i.e., M = |{(i, j) | A[i] = B[j], 1 ≤ i, j ≤ n}|.
a ●bA

●
● ●

a ●

●
●

●

●

b

● ●

●

b

● ●

●

a ●

●

●a b b a b aB

A[3] = B[5]M = # of ●’s M = O(n2)Matching Points [Cont.]
 But M can be much smaller than O(n2)in many casesei●●kooc●biscuitOur Results
Upper bounds (algorithms) for LCSS
algorithm

timespace

Naïve

O(n6)

O(n4)

SimpleO(M n4)O(n4)Matching rectangle 1O(σM 3 +n)O(M 2 +n)

Matching rectangle 2

O(M 3 log2n loglog n + n)O(M 3 +n)

M is at most O(n2)and can be much smallern is the length of the input strings.
 M is the number of matching points,i.e., M = |{(i, j) | A[i] = B[j], 1 ≤ i, j ≤ n}|.
 σ is the alphabet size.
Matching Rectangles
Tuple r = (i, j, k, l) is called matching rectangle
if A[i] = A[j] = B[k] = B[l].

ABijccklccn+1jr

i0kln+1

Partial Order of Matching Rectangles
 For matching rectangles r = (i, j, k, l) and r’ = (i’, j’, k’, l’),r < r’ iff i < i’, j < j’, k < k’, and l < l’.
Namely, r < r’ iff r lies strictly more left-lower than r’.

j’ji’r’j’r’i’r

jiri
kk’ ll’kl k’l’

Observation
 Each common square subsequence hascorresponding sequence of matching rectangles.
…
…

c…

b…

A

a
c…
…

b…

a…a…b…c…a…b…c…

BCSS and matching rectangle
 Sequence r1, …, rs of s matching rectangles

represents CSS of length s iff

 r1 < r2 ... < rs is < j1, ks < l1 where r1 = (i1, j1, k1, l1), rs = (is, js, ks, ls)

CSS and matching rectangle
 Sequence r1, …, rs of s matching rectangles

represents CSS of length s iff

 r1 < r2 ... < rs
 is < j1, ks < l1 where r1 = (i1, j1, k1, l1), rs = (is, js, ks, ls)

is strictly moreleft-lower than

LCSS → Longest sequence of DOMRs
 Computing LCSS reduces to finding longest

sequence of diagonally overlapping matchingrectangles (DOMRs).

18

Basic Algorithm
For each matching rectangle r, maintain DP table Dr of size M 2such that Dr[r’ ] stores length of longest sequence of DOMRs
that begins with r and ends with r’.

For each character c, find the “closest” matching rectangle rc
w.r.t. c that can be added after r’. Update Dr[rc] if needed.
raar’araa

Basic AlgorithmFor each matching rectangle r, maintain DP table Dr of size M 2such that Dr[r’ ] stores length of longest sequence of DOMRs
that begins with r and ends with r’.

For each character c, find the “closest” matching rectangle rcw.r.t. c that can be added after r’. Update Dr[rc] if needed.
br’rbbrbb

Basic Algorithm
For each matching rectangle r, maintain DP table Dr of size M 2such that Dr[r’ ] stores length of longest sequence of DOMRs
that begins with r and ends with r’.

For each character c, find the “closest” matching rectangle rc
w.r.t. c that can be added after r’. Update Dr[rc] if needed.
cr’rccrcc

Basic Algorithm [Cont.] Let R be # of matching rectangles ( R = O(M 2 ) ).
 We compute Dr[r’ ] for R 2 = O(M 4 ) pairs ofmatching rectangles (r, r’) .
 We test σ characters to extend the current sequenceof DOMRs w.r.t. Dr[r’ ].
 Each extension can be obtained in O(1) timeafter suitable preprocessing.
 O(σR2 + n) = O(σM 4 + n) time… Slow?
Can be improved toO(σΜ R + n) = O(σM 3 + n) timeOn Start Matching Rectangle
 Always better to use a start matching rectangle thathas the “smallest” left-lower corner for each character.
Try each matching point m for aaaaaaaaaaa

Can always use this fixed point for aaa

Improved Algorithm
 We compute Dm[r’ ] for M R = O(M 3 ) pairs ofmatching points and matching rectangles (m, r’) .
 We test σ characters to extend the current sequenceof DOMRs.
 Each extension can be obtained in O(1) timeafter suitable preprocessing.
 O(σM R + n) = O(σM 3 + n) time!

Improved Algorithm [Cont.]
Theorem
The LCSS problem can be solved inO(σM R + n) = O(σM 3 + n) time withO(M 2 + n) space.

CorollaryThe expected running time of this algorithmis O(n6/σ3 ).
For random text M ≈ n2/σ and R ≈ M 2 /σ ≈ n4/σ3.

Hardness of LCSSLemma
LCSS for two strings is at least as hard as
LCS for four strings.

4-LCS  2-LCSS
Computing LCS for A, B, C, D of length n eachreduces to computing LCSS of A’, B’ of length 4n+2 each.
ACB

D|A| = |B| = |C| = |D| = nA’$n+1$n+1B’$n+1$n+1

Conditional Lower Bound for LCSS
Lemma [Abboud et al. 2015]
There is no algorithm which solves the LCS
problem for k strings in O(nk-ε) time withconstant ε > 0, unless the strong exponential time
hypothesis (SETH) fails.

Corollary
There is no algorithm which solves the LCSS
problem for two strings in O(n4-ε) time withconstant ε > 0, unless SETH fails.

Conclusions & Open Problem
Upper bounds for LCSS

M = O(n2)algorithm

timespaceNaïve

O(n6)

O(n4)

SimpleO(M n4)O(n4)Matching rectangle 1O(σM 3 +n)O(M 2 +n)

Matching rectangle 2O(M 3 log2n loglog n + n)O(M 3 +n)

Conditional Lower bound for LCSS
O(n4-ε)-time solution (with constant ε > 0) is unlikely to exist

How can we close this (almost) quadratic gap?

Strong Exponential Time Hypothesis (SETH) Let sk be the greatest lower bound (infimum) of

real numbers δ such that k-SAT can be solved inO(2δn) time, where n = # of variables.

 The exponential time hypothesis (ETH) isa conjecture that sk > 0 for any k ≥ 3.

 Clearly s3 ≤ s4 ≤ s5 …

The strong ETH (SETH) is a conjecture thatthe limit of sk when k approaches ∞ is 1.