Page 33 - 2024F

26 UEC Int’l Mini-Conference No.53

Lemma 4 The Algorithm 1 gives the value |Q| = |Q \I|/2, and as I ⊂ Q , we have
′
′
N N |Q \I| = |Q | − |I|.
′
′
X X
ans 1 = |lcp(S[a..N], S[c..N])| in O(N)
c a
time. For each (a, b, c, d) ∈ I, let w (a,b,c,d) be the in-
Proof. Remark 3 proves that the al- tersecting substring containing both arms S[a..b]
and S[c..d], so assuming b ≤ d, w =
gorithm correctly counts for each node (a,b,c,d)
S[a..d].
v the number of pairs (a, c) such that
lcp(S[a..N], S[c..N]) = str(v). Every pair
′ ′ ′
(a, c) is processed when v = lca(ℓ(a), ℓ(c)) , Lemma 8 Let w (a,b,c,d) = uuv = u v v with
′
′
adding the value str(v) to ans 1 , thus the value |u| = |a − c| = |b − d| = |v | and |v| = |u | ≥ 1.
N N It then follows that w is in S[i..j] for
X X (a,b,c,d)
ans 1 is |lcp(S[a..N], S[c..N])|. The time exactly one run (i, j, p) ∈ Runs(S) that has a
a=1 c=1 period |a − c|.
complexity of the algorithm is linear since its Proof. Assume b ≤ d. The case b > d is solved
core is a simple depth-first traversal (with some similarly.
constant time additional computations).
Since S[a..b] = S[c..d], the substrings of length
b − a + 1 starting at index a and c are identical:
Algorithm 1 does not count the elements of it holds that w [i] = w [i + |a − c|].
(a,b,c,d)
(a,b,c,d)
the answer set Q because the condition b < c Because the two substrings intersect and form
does not hold. Nevertheless, we can assert the w , it is periodical with a period of |a − c|.
following: (a,b,c,d)
Hence, w (a,b,c,d) is part of exactly one run
(i, j, p) with np = |a − c| for some n ∈ N and
Remark 5 Let Q = {(a, b, c, d) | 1 ≤ a ≤ i ≤ a, b, c, d ≤ j.
′
b ≤ N, 1 ≤ c ≤ d ≤ N, S[a..b] = S[c..d]}. Then
ans 1 = |Q |.
′
Proof. It follows immediately from Lemma 4 Lemma 9 Let W = {(l, r, q) | i ≤ l < r ≤
(i,j,p)
and Lemma 2. j, ∃n ∈ N : np = q, 2q+1 ≤ r−l+1 ≤ j −i+1}.

[
Then, W = |I|.
′
We observe that Q ⊂ Q . We aim to find |Q| (i,j,p)
by computing |Q | and |Q | − |Q|. (i,j,p)∈Runs(S)
′
′
Proof. We first show that for each (a, b, c, d) ∈ I,
there exists a distinct (l, r, q) in exactly one
Remark 6 Let (a, b, c, d) be a tuple in Q. W .
(i,j,p)
Then (a, b, c, d) ∈ Q but also (c, d, a, b) ∈ Q and Consider (a, b, c, d) ∈ I. From Lemma 8,
′
′
(a, b, c, d) ̸= (c, d, a, b). Moreover, if (a, b, c, d) ∈ we have that w = uuv is in S[i..j]
Q and [a, b] ∩ [c, d] = ∅, then (a, b, c, d) ∈ Q or (a,b,c,d)
′
for exactly one (i, j, p) ∈ Runs(S). We set
(c, d, a, b) ∈ Q.
S[l..r] = w (a,b,c,d) = uuv. Then, since S[l..r] is
In other words, a tuple (a, b, c, d) ∈ Q “ap- a substring of S[i..j] and since |u| ≥ 1, we have
pears twice” in Q and all the elements in Q ′ i ≤ l < r ≤ j. Since from Lemma 8, S[l..r]
′
which have this property are those for which
has a period |a − c| = |u| and np = |a − c|
the substrings S[a..b] and S[c..d] do not inter- for some n ∈ N, we can set q := |u|. Since
sect (either b < c or d < a). We use Remark 6
|S[l..r]| = r − l + 1, S[l..r] = uuv, q = |u|
to compute the final answer using ans 1 and the and |v| ≥ 1, we have that 2q + 1 ≤ r − l + 1.
number of tuples (a, b, c, d) such that S[a..b] and Because S[l..r] is a substring of S[i..j] we have
S[c..d] do not intersect. that r − l + 1 ≤ j − i + 1. Thus, for every
(a, b, c, d) ∈ I, w (a,b,c,d) in run (i, j, p), there is a
Lemma 7 Let I = {(a, b, c, d) ∈ Q ′ | distinct (l, r, q) element of W (i,j,p) .
[a, b] ∩ [c, d] ̸= ∅} and ans 2 = |I|. Then the an-
swer to the Problem 1 is ans = (ans 1 −ans 2 )/2. We now show that for each (l, r, q) ∈ W (i,j,p)
Proof. From Remark 6 we have that for any run (i, j, p) ∈ Runs(S), there exists a