Dynamic index, LZ factorization, and LCE
queries in compressed space

arXiv:1504.06954v4 [] 6 Apr 2016

Takaaki Nishimoto1 , Tomohiro I2 , Shunsuke Inenaga1 , Hideo Bannai1 , and
Masayuki Takeda1
1

Department of Informatics, Kyushu University, Japan
{takaaki.nishimoto, inenaga, bannai, takeda}@inf.kyushu-u.ac.jp
2
Kyushu Institute of Technology, Japan
tomohiro@ai.kyutech.ac.jp

Abstract. In this paper, we present the following results: (1) We propose a new dynamic compressed index of O(w) space, that supports
searching for a pattern P in the current text in O(|P |f (M, w)+log w log |P | log∗ M (log N +
log |P | log ∗ M ) + occ log N ) time and insertion/deletion of a substring of
length y in O((y + log N log∗ M ) log w log N log∗ M ) time, where N is
the length of the current text, M is the maximum length of the dynamic text, z is the size of the Lempel-Ziv77 (LZ77)
factorization of
q
log a log log b
the current text, f (a, b) = O(min{ loglog
, logloglogb b }) and w =
log log a
∗
O(z log N log M ). (2) We propose a new space-efficient LZ77 factorization algorithm for a given text of length N , which runs in O(N f (N, w′ ) +
z log w′ log3 N (log∗ N )2 ) time with O(w′ ) working space, where w′ =
O(z log N log∗ N ). (3) We propose a data structure of O(w) space which
supports longest common extension (LCE) queries on the text in O(log N +
log ℓ log∗ N ) time, where ℓ is the output LCE length. On top of the above
contributions, we show several applications of our data structures which
improve previous best known results on grammar-compressed string processing.

1
1.1

Introduction
Dynamic compressed index

In this paper, we consider the dynamic compressed text indexing problem of
maintaining a compressed index for a text string that can be modiﬁed. Although
there exits several dynamic non-compressed text indexes (see e.g. [27,3] for recent work), there has been little work for the compressed variants. Hon et al. [13]
proposed the ﬁrst dynamic compressed index of O( 1ǫ (N H0 + N )) bits of space
1+ǫ
which supports searching of P in O(|P | log2 N (logǫ N + log |Σ|) +
√occ log2+ǫ N )
N)
time and insertion/deletion of a substring of length y in O((y + N ) log
amortized time, where 0 < ǫ ≤ 1 and H0 ≤ log |Σ| denotes the zeroth order
empirical entropy of the text of length N [13]. Salson et al. [29] also proposed a
dynamic compressed index, called dynamic FM-Index. Although their approach

works well in practice, updates require O(N log N ) time in the worst case. To
our knowledge, these are the only existing dynamic compressed indexes to date.
In this paper, we propose a new dynamic compressed index, as follows:
Theorem 1. Let M be the maximum length of the dynamic text to index, N
the length of the current text T , and z the number of factors in the LempelZiv 77 factorization of T without self-references. Then, there exist a dynamic
index of O(w) space which supports searching of a pattern P in O(|P |fA +
log w log |P | log∗ M (log N +log |P | log∗ M )+occ log N ) time and insertion/deletion
of a substring of length y in amortized O((y + log N log∗ M ) log w logq
N log∗ M )
log M log log w
time, where w = O(z log N log∗ M ) and fA = O(min{ loglog
,
log log M

log w
log log w }).

Since z ≥ log N , log w = max{log z, log(log∗ M )}. Hence, our index is able to
ﬁnd pattern occurrences faster than the index of Hon et al. when the |P | term is
dominating in the pattern search times. √
Also, our index allows faster substring
insertion/deletion on the text when the N term is dominating.

Related work. Our dynamic compressed index uses Mehlhorn et al.’s locally
consistent parsing and signature encodings of strings [22], originally proposed
for eﬃcient equality testing of dynamic strings. Alstrup et al. [3] showed how
to improve the construction time of Mehlhorn et al.’s data structure (details
can be found in the technical report [2]). Our data structure uses Alstrup et
al.’s fast string concatenation/split algorithms and linear-time computation of
locally consistent parsing, but has little else in common than those. In particular,
Alstrup et al.’s dynamic pattern matching algorithm [3,2] requires to maintain
speciﬁc locations called anchors over the parse trees of the signature encodings,
but our index does not use anchors.
Our index has close relationship to the ESP-indices [30,31], but there are two
signiﬁcant diﬀerences between ours and ESP-indices: The ﬁrst diﬀerence is that
the ESP-index [30] is static and its online variant [31] allows only for appending
new characters to the end of the text, while our index is fully dynamic allowing for
insertion and deletion of arbitrary substrings at arbitrary positions. The second
diﬀerence is that the pattern search time of the ESP-index is proportional to
the number occ c of occurrences of the so-called “core” of a query pattern P ,
which corresponds to a maximal subtree of the ESP derivation tree of a query
pattern P . If occ is the number of occurrences of P in the text, then it always
holds that occ c ≥ occ, and in general occ c cannot be upper bounded by any
function of occ. In contrast, as can be seen in Theorem 1, the pattern search
time of our index is proportional to the number occ of occurrences of a query
pattern P . This became possible due to our discovery of a new property of the
signature encoding [2] (stated in Lemma 12). In relation to our problem, there
exists the library management problem of maintaining a text collection (a set
of text strings) allowing for insertion/deletion of texts (see [24] for recent work).
While in our problem a single text is edited by insertion/deletion of substrings,
in the library management problem a text can be inserted to or deleted from
2

the collection. Hence, algorithms for the library management problem cannot be
directly applied to our problem.
1.2

Applications and extensions

Computing LZ77 factorization in compressed space. As an application
to our dynamic compressed index, we present a new LZ77 factorization algo∗
2
rithm for a string T of length N , running in O(N fA + z log w log3 N
q(log N ) )

log N log log w
time and O(w) working space, where fA = O(min{ loglog
, logloglogww }).
log log N
Goto et al. [11] showed how, given the grammar-like representation for string
T generated by the LCA algorithm [28], to compute the LZ77 factorization of
T in O(z log2 m log3 N + m log m log3 N ) time and O(m log2 m) space, where
m is the size of the given representation. Sakamoto et al. [28] claimed that
m = O(z log N log∗ N ), however, it seems that in this bound they do not consider the production rules to represent maximal runs of non-terminals in the
derivation tree. The bound we were able to obtain with the best of our knowledge and understanding is m = O(z log2 N log∗ N ), and hence our algorithm
seems to use less space than the algorithm of Goto et al. [11]. Recently, Fischer
et al. [10] showed a Monte-Carlo randomized algorithms to compute an approximation of the LZ77 factorization with at most 2z factors in O(N log N ) time,
and another approximation with at most (i + ǫ)z factors in O(N log2 N ) time for
any constant ǫ > 0, using O(z) space each. Another line of research is a recent
result by Policriti and Prezza [25] which uses N H0 + o(N log |Σ|) + O(|Σ| log N )
bits of space and computes the LZ77 factorization in O(N log N ) time.

Longest common extension queries in compressed space. Furthermore,
we consider the longest common extension (LCE) problems on: an uncompressed
string T of length N ; a grammar-compressed string T represented by an straightline program (SLP) of size n, or an LZ77-compressed string T with z factors. The
best known deterministic LCE data structure on SLPs is due to I et al. [15], which
supports LCE queries in O(h log N ) time each, occupies O(n2 ) space, and can
be built in O(hn2 ) time, where h is the height of the derivation tree of a given
SLP. Bille et al. [5] showed a Monte Carlo randomized data structure built on
a given SLP of size n which supports LCE queries in O(log N log ℓ) time each,
where ℓ is the output of the LCE query and N is the length of the uncompressed
text. Their data structure requires only O(n) space, but requires O(N ) time to
construct. Very recently, Bille et al. [6] showed a faster Monte Carlo randomized
data structure of O(n) space which supports LCE queries in O(log N + log2 ℓ)
time each. The preprocessing time of this new data structure is not given in [6].
In this paper, we present a new, deterministic LCE data structure using
compressed space, namely O(w) space, supporting LCE queries in O(log N +
log ℓ log∗ N ) time each. We show how to construct this data structure in O(N log w)
time given an uncompressed string of length N , O(n log log n log N log∗ N ) time
given an SLP of size n, and O(z log w log N log∗ N ) time given the LZ77 factorization of size z. We remark that our new LCE data structure allows for fastest
3

deterministic LCE queries on SLPs, and even permits faster LCE queries than
the randomized data structure of Bille et al. [6] when log∗ N = o(log ℓ) which in
many cases is true.
All proofs omitted due to lack of space can be found in the appendices.

2
2.1

Preliminaries
Strings

Let Σ be an ordered alphabet and $ be the lexicographically largest character in
Σ. An element of Σ ∗ is called a string. For string w = xyz, x is called a preﬁx,
y is called a substring, and z is called a suﬃx of w, respectively. The length of
string w is denoted by |w|. The empty string ε is a string of length 0, that is,
|ε| = 0. Let Σ + = Σ ∗ − {ε}. For any 1 ≤ i ≤ |w|, w[i] denotes the i-th character
of w. For any 1 ≤ i ≤ j ≤ |w|, w[i..j] denotes the substring of w that begins
at position i and ends at position j. Let w[i..] = w[i..|w|] and w[..i] = w[1..i]
for any 1 ≤ i ≤ |w|. For any string w, let wR denote the reversed string of w,
that is, wR = w[|w|] · · · w[2]w[1]. For any strings w and u, let LCP(w, u) (resp.
LCS(w, u)) denote the length of the longest common preﬁx (resp. suﬃx) of w
and u. Given two strings s1 , s2 and two integers i, j, let LCE(s1 , s2 , i, j) denote
a query which returns LCP(s1 [i..|s1 |], s2 [j..|s2 |]).
For any strings p and s, let Occ(p, s) denote all occurrence positions of p in
s, namely, Occ(p, s) = {i | p = s[i..i + |p| − 1], 1 ≤ i ≤ |s| − |p| + 1}.
In this paper, we deal with a dynamic text, namely, we allow for insertion/deletion of a substring to/from an arbitrary position of the text. Let M be
the maximum length of the dynamic text to index. Our model of computation
is the unit-cost word RAM with machine word size of log2 M bits, and space
complexities will be evaluated by the number of machine words. Bit-oriented
evaluation of space complexities can be obtained with a log2 M multiplicative
factor.
Lempel-Ziv 77 factorization. We will use the Lempel-Ziv 77 factorization [32]
of a string to bound the running time and the size of our data structure on the
string. It is a greedy factorization which scans the string from left to right, and
recursively takes as a factor the longest preﬁx of the remaining suﬃx with a
previous occurrence. Formally, it is deﬁned as follows.
Definition 1 (Lempel-Ziv77 Factorization [32]). The Lempel-Ziv77 (LZ77)
factorization of a string s without self-references is a sequence f1 , . . . , fz of nonempty substrings of s such that s = f1 · · · fz , f1 = s[1], and for 1 < i ≤ z, if the
character s[|f1 ..fi−1 |+1] does not occur in s[|f1 ..fi−1 |], then fi = s[|f1 ..fi−1 |+1],
otherwise fi is the longest prefix of fi · · · fz which occurs in f1 · · · fi−1 .

The size of the LZ77 factorization f1 , . . . , fz of string s is the number z of factors
in the factorization.
A variant of LZ77 factorization which allows for self-overlapping reference to
a previous occurrence is formally deﬁned as follows.
4

Definition 2 (Lempel-Ziv77 Factorization with self-reference [32]). The
Lempel-Ziv77 (LZ77) factorization of a string s with self-references is a sequence
f1 , . . . , fk of non-empty substrings of s such that s = f1 · · · fk , f1 = s[1], and for
1 < i ≤ k, if the character s[|f1 ..fi−1 | + 1] does not occur in s[|f1 ..fi−1 |], then
fi = s[|f1 ..fi−1 | + 1], otherwise fi is the longest prefix of fi · · · fk which occurs
at some position p, where 1 ≤ p ≤ |f1 · · · fi−1 |.
We will show that using our data structure, the LZ77 with self-reference can be
computed eﬃciently in compressed space.
Locally consistent parsing. Let p be a string of length n over an integer
alphabet of size W where any adjacent elements are diﬀerent, i.e., p[i] 6= p[i +
1] for all 1 ≤ i < n. A locally consistent parsing [22] of p is a parsing (or
factorization) q1 , . . . , qj of p such that p = q1 · · · qj , 2 ≤ |qh | ≤ 4 for any 1 ≤ h ≤
j, and the boundary between qh−1 and qh is “determined” by p[|q1 · · · qh−1 | +
1 − ∆L ..|q1 · · · qh−1 | + 1 + ∆R ], where ∆L = log∗ W + 6 and ∆R = 4. Clearly,
j ≤ n/2. By “determined” above, we mean that if a position i of an integer
string p and a position k of another integer string s share the same left context
of length at least ∆L and the same right context of length at least ∆R , then
there is a boundary of the locally consistent parsing of p between the positions
i − 1 and i iﬀ there is a boundary of the locally consistent parsing of s between
the positions k − 1 and k. A formal deﬁnition of locally consistent parsing, and
its linear-time computation algorithm, is explained in the following lemma.
Lemma 1 (Locally consistent parsing [22,2]). Let W be a non-negative
integer and let p be an integer sequence of length n, called a W -colored sequence,
where p[i] 6= p[i + 1] for any 1 ≤ i < n and 0 ≤ p[j] ≤ W for any 1 ≤ j ≤ n. For
∗
every W there exists a function f : [−1..W ]log W +11 → {0, 1} such that for every
W -colored sequence p, the bit sequence d defined by d[i] = f (p̃[i − ∆L ], . . . , p̃[i +
∆R ]) for 1 ≤ i ≤ n, satisfies:
– d[1] = 1,
– d[i] + d[i + 1] ≤ 1 for 1 ≤ i < n, and
– d[i] + d[i + 1] + d[i + 2] + d[i + 3] ≥ 1 for any 1 ≤ i < n − 3,
where ∆L = log∗ W + 6, ∆R = 4, and p̃[j] = p[j] for all 1 ≤ j ≤ n, p̃[j] = −1
otherwise. Furthermore, d can be computed in O(n) time using a precomputed
table of size o(log W ). Also, we can compute this table in o(log W ) time.
Proof. Here we give only an intuitive description of a proof of Lemma 1. More
detailed proofs can be found at [22] and [2].
Mehlhorn et al. [22] showed that there exists a function f ′ which returns
a (log W )-colored sequence p′ for a given W -colored sequence p in O(|p|) time,
where p′ [i] is determined only by p[i − 1] and p[i] for 1 ≤ i ≤ |p|. Let phki denote
the outputs after applying f ′ to p by k times. They also showed that there
exists a function f ′′ which returns a bit sequence d satisfying the conditions of
Lemma 1 for a 6-colored sequence p in O(|p|) time, where d[i] is determined only
5

by p[i−3..i+3] for 1 ≤ i ≤ |p|. Hence we can compute d for a W -colored sequence
∗
∗
p in O(|p| log∗ W ) time by applying f ′′ to phlog W +2i after computing phlog W +2i .
Furthermore, Alstrup et al. [2] showed that d can be computed in O(|p|) time
using a precomputed table of size o(log W ). The idea is that ph3i is a log log log W colored sequence and the number of all combinations of a log log log W -colored
∗
sequence of length log∗ W + 11 is 2(log W +11) log log log W = o(log W ). Hence we
can compute d for a W -colored sequence in linear time using a precomputed
table of size o(log W ).
⊓
⊔
Given a bit sequence d of Lemma 1, let Eblock d (p) be the function that
decomposes an integer sequence p into a sequence q1 , . . . , qj of substrings called
blocks of p, such that p = q1 · · · qj and qi is in the decomposition iﬀ d[|q1 · · · qi−1 |+
1] = 1 for any 1 ≤ i ≤ j. We omit d and write Eblock d (p) when it is clear from
the context, and we use implicitly the bit sequence created by Lemma 1 as d.
Let |Eblock (p)| = j and let Eblock (s)[i] = qi . For a string s, let Epow (s) be the
function which groups each maximal run of same characters a as ar , where r is
the length of the run. Epow (s) can be computed in O(|s|) time. Let |Epow (s)|
denote the number of maximal runs of same characters in s and let Epow (s)[i]
denote i-th maximal run in s.
Example 1 (Eblock d (p) and Epow (s)). Let log∗ W = 2, and then ∆L = 8, ∆R =
4.
If p = 1, 2, 3, 2, 5, 7, 6, 4, 3, 4, 3, 4, 1, 2, 3, 4, 5 and d = 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0,
then Eblock d (p) = (1, 2, 3), (2, 5), (7, 6, 4), (3, 4, 3, 4), (1, 2), (3, 4, 5), |Eblock d (p)| =
6 and Eblock d (p)[2] = (2, 5). For string s = aabbbbbabb, Epow (s) = a2 b5 a1 b2 and
|Epow (s)| = 4 and Epow (s)[2] = b5 .
2.2

Context free grammars as compressed representation of strings

Admissible context free grammars. An admissible context free grammar
(ACFG) [18] is a CFG which generates only a single string. More formally, an
ACFG that generates a single string T is a quadruple G = (Σ, V, D, S), such
that
– Σ is an ordered alphabet of terminal characters,
– V = {e1 , . . . , ek } is a set of positive integers with e1 < · · · < ek , called
variables,
– D = {ei → xexpr i }ki=1 is a set of deterministic productions (or assignments)
i.e., for each variable e ∈ V there is exactly one production in D whose
lefthand side is e,
– each ei ∈ V \ {S} appears at least once in the righthand side of some production ej → xexpr j with ei < ej , and
– S ∈ V is the start symbol which derives the string T .
Sometimes we handle a variable sequence as a kind of string. For example, for
any variable sequence y = ei1 · · · eid ∈ V + , let |y| = d and y[c] = eic for 1 ≤ c ≤ d.
Let val : V → Σ + be the function which returns the string derived by an input
6

variable. If s = val (e) for e ∈ V, then we say that the variable e represents string
s. For any variable sequence y ∈ V + , let val + (y) = val (y[1]) · · · val (y[|y|]).
For two variables e1 , e2 ∈ V, we say that e1 occurs at position c in e2 if there
is a node labeled with e1 in the derivation tree of e2 and the leftmost leaf of
the subtree rooted at that node labeled with e1 is the c-th leaf in the derivation
tree of e2 . Furthermore, for variable sequence y ∈ V + , we say that y occurs at
position c in e if y[i] occurs at position c+|val + (y[..i−1])| in e for 1 ≤ i ≤ |y|. We
deﬁne the function vOcc(e1 , e2 ) which returns all positions of e1 in the derivation
tree of e2 .
Straight-line programs. A straight-line program (SLP ) is an ACFG in the
Chomsky normal from. Formally, SLP S of size n is an ACFG G = (Σ, V, D, Xn ),
where V = {X1 , · · · , Xn }, val (Xn ) = T , D = {Xi → expr i }ni=1 with each expr i
being either of form Xℓ Xr (1 ≤ ℓ, r < i), or a single character a ∈ Σ. The size of
the SLP G is the number n of productions in D. In the extreme cases the length
N of the string T can be as large as 2n−1 , however, it is always the case that
n ≥ log2 N . For any variable Xi with Xi → Xℓ Xr ∈ D, let Xi .left = val (Xℓ )
and Xi .right = val (Xr ), which are called the left string and the right string of
Xi , respectively.
Example 2 (SLP). Let S = (Σ, V, D, S) be the SLP s.t. Σ = {A, B, C}, V =
{X1 , · · · , X11 }, D = {X1 → A, X2 → B, X3 → C, X4 → X3 X1 , X5 → X4 X2 , X6 →
X5 X5 , X7 → X2 X3 , X8 → X1 X2 , X9 → X7 X8 , X10 → X6 X9 , X11 → X10 X6 },
S = X11 , the derivation tree of S represents CABCABBCABCABCAB.
Run-length ACFGs. We deﬁne run-length ACFGs as an extension to ACFGs,
which allow run-length encodings in the righthand sides of productions. Formally,
a run-length ACFG is G = (Σ, V, D, S), where D = {ei → xexpr i }w
i=1 , val (S) =
T and each xexpr i is in one of the following forms:


a ∈ Σ,
xexpr i = eℓ er ∈ V +
(eℓ , er < ei ),

 d
ê ∈ V × N (ê < ei , and d > 1).

Hence xexpr i ∈ Σ ∪ V + ∪ (V × N ). The size of the run-length ACFG G is the
number w of productions in D.
Let Sig G : Σ ∪ V + ∪ (V × N ) → V be the function such that


if (e → x ) ∈ D,
e
Sig G (x ) = Sig G (Sig G (x[1..|x| − 1])x[|x|]) if x[i] ∈ V for 1 ≤ i ≤ |x|, 2 < |x| ≤ 4,


undeﬁned
otherwise.

Namely, the function Sig G returns, if any, the lefthand side of the corresponding
production for a given element in Σ ∪V + ∪(V ×N ) of length 3 or 4, by recursively
applying the Sig function from left to right. Let Assgn G be the function such that
7

Assgn G (ei ) = xexpri iﬀ ei → xexpri ∈ D. When clear from the context, we write
Sig G and Assgn G as Sig and Assgn, respectively. For any p ∈ (Σ ∪V + ∪(V ×N ))∗ ,
let Sig + (p) = Sig(p[1]) · · · Sig(p[|p|]). We deﬁne the left and right strings for
any variable ei → eℓ er ∈ D in a similar way to SLPs. Furthermore, for any
ei → êk ∈ D, let ei .left = val (ê) and ei .right = val (ê)k−1 .
In this paper, we consider a DAG of size w that is a compact representation
of the derivation trees of variables in a run-length ACFG G, where each node
represents a variable in V and out-going edges represent the assignments in D.
For example, if there exists an assignment ei → eℓ er ∈ D, then there exist two
out-going edges from ei to its ordered children eℓ and er . In addition, eℓ and er
have reversed edges to their parent ei . For any e ∈ V, let parents(e) be the set
of variables which have out-going edge to e in the DAG of G. If a node is labeled
by e, then the node is associated with |val (e)|.
Example 3 (Run-length ACFG). Let G = (Σ, V, D, S) be a run-length ACFG,
where Σ = {A, B, C}, V = {1, . . . , 15}, D = {1 → A, 2 → B, 3 → C, 4 →
34 , 5 → 11 , 6 → 21 , 7 → 31 , 8 → (7, 5), 9 → (8, 6), 10 → (5, 6), 11 → (10, 4), 12 →
92 , 13 → 107 , 14 → 111 , 15 → (12, 13), 16 → (15, 14), 17 → 161 }, and S =
17. The derivation tree of the start symbol S represents a single string T =
CABCABABABABABABABABABCCCC. Here, 4.left = val (3), 4.right =
val + (33 ), Sig((7, 5)) = 8, Sig((7, 5, 6)) = 9, Sig((6, 5)) = undeﬁned, parents(5) =
{8, 10} and vOcc(9, 17) = {1, 4}. See also Fig. 1 in Section 3 which illustrates
the derivation tree of the start symbol S and the DAG for G.
Dynamization and data structure of run-length ACFG. In this paper,
we consider a compressed representation and compressed index of a dynamic
text based on run-length ACFGs. Hence, upon edits on the text, the run-length
ACFG representing the text needs to be modiﬁed as well. To this end, we consider
dynamic run-length ACFGs, which allow for insertion of new assignments to D,
and allow for deletion of assignments e → xexpr from D only if |parents(e)| = 0.
We remark that the grammar under modiﬁcation may temporarily represents
more than one text, however, this will be readily ﬁxed as soon as we insert a
new start symbol of the grammar representing the edited text.
′
Next, we consider an abstract data structure H(fA , fA
) to maintain a dynamic run-length ACFG G = (Σ, V, D, S) of size w. H consists of two compo′
nents A and B. The ﬁrst component A is an abstract data structure of O(fA
) size
which is able to add/remove an assignment to/from D in O(fA ) time. This data
structure is also able to compute Sig(xexpr) in O(fA ) time. For example, using
a balanced binary search tree for D, we achieve deterministic fA = O(log w)
′
time and fA
= O(w) space. Note that using the best known deterministic predecessor/successor data
for a dynamic
integers [4], we achieve
q set ofo
 structure
n
deterministic fA = O min

log log M log log w
,
log log log M

log w
log log w

′
time and fA
= O(w)

space, where M is the maximum length of the dynamic text3 . The second compo3

Alstrup et al. [2] used hashing to maintain A and obtained a randomized H(1, w)
signature dictionary. However, since we are interested in the worst case time com-

8

nent B is the DAG of G introduced in the previous subsection. The corresponding
nodes and edges of the DAG can be added/deleted in constant time per addition/deletion of an assignment. By maintaining parents(e) with a doubly-linked
list for each node ve representing a variable e ∈ V, we obtain the following lemma:
′
Lemma 2. Using H(fA , fA
) for a dynamic run-length ACFG G = (Σ, V, D, S)
of current size w, Sig(xexpr) can be computed in O(fA ) time, for a given xexpr ∈
Σ∪V + ∪(V ×N ). Given a node ve representing a variable e, Assgn(e) and |val (e)|
can be computed in O(1) time, and parents(e) can be computed in O(|parents(e)|)
time. We can also update H in O(fA ) time when an assignment is added to/removed
from D.

Note that Assgn(e), Sig(xexpr ) and parents(e) can return not only the signatures
but also the corresponding nodes in the DAG.

3

Signature encoding

In this section, we recall the signature encoding ﬁrst proposed by Mehlhorn
et al. [22]. The signature encoding of a string T is a run-length ACFG G =
(Σ, V, D, S) where the assignments in D are determined by recursively applying
to T the locally consistent parsing, the Encblock function, and the Sig function
(recall Section 2), until a single integer S is obtained. More formally, we use the
Shrink and Pow functions in the signature encoding of string T deﬁned below:

Shrink Tt

=

(

Sig + (T )
for t = 0
+
T
Sig (Eblock (Pow t−1 )) for 0 < t ≤ h,

Pow Tt = Sig + (Epow (Shrink Tt ))

for 0 ≤ t ≤ h,

where h is the minimum integer satisfying |Pow Th | = 1. Then, the start symbol
of the signature encoding is S = Pow Th , and the height of the derivation tree of
the signature encoding of T is O(h) = O(log N ), where N = |T | (see also Fig. 1
below).
Example 4 (Signature encoding). Let G = (Σ, V, D, S) be a run-length ACFG
of Example 3. Assuming Eblock (Pow T0 ) = (7, 5, 6), (7, 5, 6), (5, 6)7, (5, 6, 4) and
Eblock (Pow T1 ) = (12, 13, 14) hold, G is the signature encoding of T and id (T ) =
17. See Fig. 1 for an illustration of the derivation tree of G and the corresponding
DAG.
Each variable of the signature encoding (the run-length ACFG deﬁned this
way) is called a signature. For any string P ∈ Σ + , let id (T ) = Pow Th = S, i.e.,
the integer S is the signature of T .
plexities, we use balanced binary search trees or the data structure [4] in place of
hashing.

9

The signature encoding of a text T can be eﬃciently maintained under insertion/deletion of arbitrary substrings to/from T . For this purpose, we use the
′
H(fA , fA
) data structure for the signature encoding of a dynamic text.
3.1

Properties of signature encodings

Here we describe a number of useful properties of signature encodings. The
ones with references to the literature are known but we provide their proofs for
completeness. The other ones without references are our new discoveries.
Substring extraction. By the deﬁnition of the Eblock function and Lemma 1,
for any 1 ≤ t ≤ h, |Shrink Tt | ≤ |Pow Tt−1 |/2 and |Pow Tt | ≤ |Pow Tt−1 |/2. Thus
h ≤ log |s| and the height of the derivation tree of e is O(log |val (e)|) for any
signature e ∈ V. Since each node of the DAG for a signature encoding stores the
length of the corresponding string, we have the following:
Fact 1 Using the DAG for a signature encoding G = (Σ, V, D, S) of size w, given
a signature e ∈ V (and its corresponding node in the DAG), and two positive
integers i, k, we can compute val (e)[i..i + k − 1] in O(log |val (e)| + k) time.
Space requirement of the signature encoding. Recall that we handle dynamic text of length at most M . Then, the maximum value of the signatures is
bounded by 3M − 1, since the derivation tree can contain at most M leaves, and
2M − 1 internal nodes (when there are no runs of same signatures at any height
of the derivation tree, Pow function generates as many signatures as the Shrink
function). We also remark that the input of the Eblock function is a sequence
of signatures. Hence, ∆L of Lemma 1 is bounded by log∗ 3M + 6 = O(log∗ M ).
Note that we can bound M = Θ(|T |) if we do not update G after we compute
id (T ).
Let N be the length of the current text T . The size w of the signature
encoding of T is bounded by 3N − 1 by the same reasoning as above. Also, the
following lemma shows that the signature encoding of T requires only compressed
space:
Lemma 3 ([26]). The size w of the signature encoding of T is O(z log N log∗ M ),
where z is the number of factors in the LZ77 factorization without self-reference
of T .
Proof. See Appendix A.
Hence, we have w = O(min{z log N log∗ M, N }). In the sequel, we assume
z log N log∗ M ≤ N and will simply write w = O(z log N log∗ M ), since otherwise
we can use some uncompressed dynamic text index in the literature.
10

Common sequences to all occurrences of same substrings. Here, we
recall the most important property of the signature encoding.
Let G = (Σ, V, D, S) be the signature encoding of text T . Let i, j (i < j) be
any positions in T , and let P = T [i..j]. Let Pi and Pj be the paths from the
root of the derivation tree of G to the ith and jth leaves, respectively. Then, at
each depth ℓ of the derivation tree of G, consider the sequence si,j,ℓ of signatures
which lie to the right of Pi with oﬀset ∆L + 3 and to the left of Pj with oﬀset
∆R + 2. By the property of locally consistent parsing of Lemma 1, si,j,ℓ = si′ ,j ′ ,ℓ
for any occurrences [i′ ..j ′ ] of P in T and for any depth ℓ. We call each signature
contained in si,j,ℓ a consistent signature w.r.t. P .
Formally, we deﬁne the consistent signatures of P in the derivation tree of G
by the XShrink and XPow functions below, where the preﬁx of length at least ∆L
and the suﬃx of length at least ∆R + 1 are “ignored” at each depth of recursion:
Definition 3. For a string P , let
(
Sig + (P )
P
XShrink t =
P
P
P
Sig + (Eblock d (XPow P
t−1 )[|Lt |..|XPow t−1 | − |Rt |])

for t = 0,
for 0 < t ≤ hP ,

P
P
+
P
P
P
XPow P
t = Sig (Epow (XShrink t [|L̂t | + 1..|XShrink t | − |R̂t ])|) for 0 ≤ t < h ,

where
P
P
– LP
t is the shortest prefix of XPow t−1 of length at least ∆L such that d[|Lt | +
1] = 1,
– RtP is the shortest suffix of XPow P
t−1 of length at least ∆R + 1 such that
d[|d| − |RtP | + 1] = 1,
P
P
– L̂P
t is the longest prefix of XShrink t such that |Epow (L̂t )| = 1,
P
– R̂tP is the longest suffix of XShrink t such that |Epow (R̂tP )| = 1, and
– and hP is the minimum integer such that |Epow (XShrink P
hP )| ≤ ∆L +∆R +9.
P
Note that ∆L ≤ |LP
t | ≤ ∆L + 3 and ∆R + 1 ≤ |Rt | ≤ ∆R + 4 hold by the
P
deﬁnition. Hence |XShrink t+1 | > 0 holds if |Epow (XShrink P
t )| > ∆L + ∆R +
9. See Fig. 2 for illustrations of consistent signatures of each occurrence of P
in T , which are represented by the gray boxes. Since at each depth we have
“ignored” the left and right contexts of respective length at most ∆L + 3 and
∆R + 4, the consistent signatures at each depth are determined only by the
consistent signatures at the previous depth (1 level deeper). This implies that
for any occurrences of P in T , there are common consistent signatures (gray
boxes), which will simply be called the common signatures of P . The next lemma
formalizes this argument.

Lemma 4 (common sequences [26]). Let G = (Σ, V, D, S) be the signature
encoding of text T and let P be any string. Then there exists a common sequence
v = e1 , . . . , ed of signatures w.r.t. G which satisfies the following three conditions:
(1) val + (v) = P , (2) |Epow (v)| = O(log |P | log∗ M ), and (3) for any e ∈ V and
integer i such that val (e)[i..i + |P | − 1] = P , v occurs at position i in e.
11

Proof. We consider the following short sequence Uniq(P ) of signatures which
represents P (see also Fig. 2):
P
P
P
P
P
P
P P
Uniq(P ) = L̂P
0 L0 · · · L̂hP −1 LhP −1 XShrink hP RhP −1 R̂hP −1 · · · R0 R̂0 ,

where hP is the minimum integer such that |Epow (XShrink P
hP )| ≤ ∆L + ∆R + 9.
We show Lemma 4 using Uniq(P ), namely, we show v = Uniq(P ) satisﬁes all
conditions (1)-(3). (1) This follows from Deﬁnition 3 (see also Fig. 2(2)). (2)
P
P
P
|Epow (XShrink P
hP )| ≤ ∆L + ∆R + 9, h ≤ log |P |, |Lt | = Θ(∆L ), |Rt | = Θ(∆R )
P
P
and |Epow (L̂P
t )| = |Epow (R̂t )| = 1 for 1 ≤ t ≤ h . Hence |Epow (Uniq(P ))| =
O(log |P | log∗ M ). (3) For simplicity, here we only consider the case where val (e) =
T , since other cases can be shown similarly. Consider any integer i with T [i..i +
|P | − 1] = P (see also Fig. 2(2)). Note that for 0 ≤ t < hP , if XShrink P
t occurs
T
P
in Shrink Tt , then XPow P
always
occurs
in
Pow
,
because
XPow
is
determined
t
t
t
P
T
P
only by XShrink P
t . Similarly, for 0 < t ≤ h , if XPow t−1 occurs in Pow t−1 ,
P
T
then XShrink P
t always occurs in Shrink t . Since XShrink 0 occurs at position i
T
P
P
in Shrink 0 , XShrink t and XPow t occur in the derivation tree of id (T ). Hence
P
we discuss the positions of XShrink P
t and XPow t . Now, let ĉt + 1 and ct +
1 be the beginning positions of the corresponding occurrence of XShrink P
t in
T
T
Shrink Tt and that of XPow P
t in Pow t , respectively. Then Shrink t [..ĉt ] consists of
T
T
P
Pow Tt−1 [..ct−1 ] and LP
t−1 for 0 < t ≤ h . Also, Pow t [..ct ] consists of Shrink t [..ĉt ]
P
P
and L̂t for 0 ≤ t < h . This means that Uniq(P ) occurs at position i in id (T ).
Therefore Lemma 4 holds.
⊓
⊔
The sequence v of signatures in Lemma 4 is called a common sequence of P =
val (e)[i..i + k − 1] w.r.t. G. Lemma 4 implies that any substring P of T can be
represented by a sequence p of signatures with |Epow (p)| = O(log |P | log∗ M ).
The common sequences are conceptually equivalent to the cores [20] which are
deﬁned for the edit sensitive parsing of a text, a kind of locally consistent parsing
of the text.
The number of ancestors of nodes corresponding to Uniq(P ) is upper bounded
by the next lemma.
Lemma 5. Let T and P be strings, and let T be the derivation tree of the
signature encoding of T . Consider an occurrence of P in T , and the induced
subtree X of T whose root is the root of T and whose leaves are the parents of
the nodes representing Uniq(P ). Then X contains O(log∗ M ) nodes for every
height and O(log |T | + log |P | log∗ M ) nodes in total.
Proof. By Deﬁnition 3, for every height, X contains O(log∗ M ) nodes that are
parents of the nodes representing Uniq(P ). Lemma 5 holds because the number
of nodes at some height is halved when Shrink is applied. More precisely, considering the x nodes of X at some height to which Shrink is applied, the number
of their parents is at most (x + 2)/2.
The next Lemma immediately follows from Lemma 5, which will be mainly
used in the proof of Lemma 3 in Appendix and the proof of Lemma 9.
12

Lemma 6. Let s1 , s2 , s3 be any strings such that s3 = s1 s2 , and let T be
the derivation tree of id (s3 ). Consider the induced subtree X of T whose root
is the root of T and whose leaves are the parents of the nodes representing
Uniq(s1 )Uniq(s2 ) (see also Fig. 2(4)). Then the size of X is O(log |s3 | log∗ M ).
The following lemma is about the computation of a common sequence of P .
Lemma 7. Using the DAG for a signature encoding G = (Σ, V, D, S) of size w,
given a signature e ∈ V (and its corresponding node in the DAG) and two integers
i and k, we can compute Epow (Uniq(s[i..i + k − 1])) in O(log |s| + log k log∗ M )
time, where s = val (e).
Proof. Let v be the common sequence of nodes which represents Uniq(s[i..i+k −
1]) and occurs at position i in e. Starting at the given node in the DAG which
corresponds to e, we compute the induced subtree which represents Uniq(s[i..i +
k − 1]), rooted at the lowest common ancestor of the nodes in v. By Lemma 5,
the size of this subtree is O(log |s| + log k log∗ M ). We can obtain the root of
this subtree in O(log |s|) time from the node representing e. Hence Lemma 7
holds.
⊓
⊔
The next lemma shows that we can compute LCE eﬃciently using the signature encoding of the (dynamic) text.
Lemma 8. Using the DAG for a signature encoding G = (Σ, V, D, S) of size
R
w, we can support queries LCE(s1 , s2 , i, j) and LCE(sR
1 , s2 , i, j) in O(log |s1 | +
∗
log |s2 | + log ℓ log M ) time for given two signatures e1 , e2 ∈ V and two integers
1 ≤ i ≤ |s1 |, 1 ≤ j ≤ |s2 |, where s1 = val (e1 ), s2 = val (e2 ) and ℓ is the answer
to the LCE query.
R
Proof. We focus on LCE(s1 , s2 , i, j) as LCE(sR
1 , s2 , i, j) is supported similarly.
Let P denote the longest common preﬁx of s1 and s2 . Our algorithm simultaneously traverses two derivation trees rooted at e1 and e2 and computes P
by matching the common signatures greedily from left to right. Since Uniq(P )
occurs at position i in e1 and at position j in e2 by Lemma 4, we can compute P
by at least ﬁnding the common sequence of nodes which represents Uniq(P ), and
hence, we only have to traverse ancestors of such nodes. By Lemma 5, the number of nodes we traverse, which dominates the time complexity, is upper bounded
by O(log |s1 | + log |s2 | + Epow (uniqP )) = O(log |s1 | + log |s2 | + log ℓ log∗ M ).
⊓
⊔

Construction Recall that a signature encoding G generating a string T is
represented and maintained by a data structure H. We show how to construct
′
an H(log w, w) or H(fA , fA
) for G. It can be constructed from various types of
inputs, such as (1) a plain (uncompressed) string T , (2) the LZ77 factorization of
T , and (3) an SLP which represents T , as summarized by the following theorem.

13

Theorem 2. 1. Given a string T of length N , we can construct H(log w, w)
for the signature encoding of size w which represents T in O(N ) time and
′
′
working space, or H(fA , fA
) in O(N fA ) time and O(fA
+ w) working space.
2. Given f1 , . . . , fz LZ77 factors without self reference of size z representing T
′
of length N , we can construct H(fA , fA
) for the signature encoding of size
′
w which represents T in O(zfA log N log∗ M ) time and O(fA
+ w) working
space.
3. Given an SLP S = {Xi → expr i }ni=1 of size n representing T of length N ,
we can construct H(log w, w) for the signature encoding of size w which represents T in O(n log log n log N log∗ M ) time and O(n log∗ M + w) working
′
′
space, or H(fA , fA
) in O(nfA log N log∗ M ) time and O(fA
+ w) working
space.
Proof. See Appendix A.
In the static case, the M term of Theorem 2 can be replaced with N .
Update In Section 4, we describe our dynamic index using H for a signature
encoding G generating a string T . For this end, we consider the following update
operations for G using H.
– INSERT (Y, i): Given a string Y and an integer i, update H. Updated H
handles a signature encoding G generates T ′ = T [..i − 1]Y [1..|Y |]T [i..].
– DELETE (i, k): Given two integers i, k, update H. Updated H handles a
signature encoding G generates T ′ = T [..i − 1]T [i + k..].

During updates, a new assignment e → xexpr is appended to G whenever it is
needed, in this paper, where e = max V + 1 that has not been used as a signature.
Speciﬁcally, we assign new signature to xeptr when Sig(xeptr ) returns undeﬁned
for some form xeptr during updates. Also, updates may produce a redundant
signature whose parents in the DAG are all removed. To keep G admissible, we
remove such redundant signatures from G during updates.

′
Lemma 9. Using H(fA , fA
) for a signature encoding G = (Σ, V, D, S) of size w
which generates T , we can support INSERT (i, Y ) and DELETE (i, k) in O(fA (k+
log N log∗ M )) time, where |Y | = k.

Proof. We support DELETE (i, k) as follows: (1) Compute a new start variable S ′ = id (T [..i − 1]T [i..]) by recomputing the new signature encoding from
Uniq(T [..i − 1]) and Uniq(T [i + k..]). This can be done in O(fA log N log∗ M )
′
time by Lemmas 7 and 6. (2) Remove all redundant signatures Z from H(fA , fA
).
Note that if a signature is redundant, then all the signatures along the path from
S to it are also redundant. Hence, we can remove all redundant signatures eﬃciently by depth-ﬁrst search starting from S, which takes O(fA |Z|) time, where
|Z| = O(k + log N log∗ M ) by Lemma 6.
Similarly, we can compute INSERT operation in O(fA (|Y | + log N log∗ M ))
time by creating S ′ using Uniq(T [..i − 1]), Uniq(Y ) and Uniq(T [i + k..]). Note
that we can naively compute id (s) for a given string s ∈ Σ + in O(fA |s|) time.
Therefore Lemma 9 holds.
⊓
⊔
14

4

Dynamic Compressed Index

In this section, we present our dynamic compressed index based on signature
encoding. As already mentioned in Section 1.1, our strategy for pattern matching
is diﬀerent from that of Alstrup et al. [2]. It is rather similar to the one taken in
the static index for SLPs of Claude and Navarro [8]. Besides applying their idea
to run-length ACFGs, we show how to speed up pattern matching by utilizing
the properties of signature encodings.
The rest of this section is organized as follows: In Section 4.1, we brieﬂy
review the idea for the SLP index of Claude and Navarro [8]. In Section 4.2, we
extend their idea to run-length ACFGs. In Section 4.3, we consider an index on
signature encodings and improve the running time of pattern matching by using
the properties of signature encodings. In Section 4.4, we show how to dynamize
our index.
4.1

Static Index for SLP

We review how the index in [8] for SLP S generating a string T computes
Occ(P, T ) for a given string P . The key observation is that, any occurrence of P
in T can be uniquely associated with the lowest node that covers the occurrence
of P in the derivation tree. As the derivation tree is binary, if |P | > 1, then the
node is labeled with some variable X ∈ V such that P1 is a suﬃx of X.left and
P2 is a preﬁx of X.right, where P = P1 P2 with 1 ≤ |P1 | < |P |. Here we call the
pair (X, |X.left| − |P1 | + 1) a primary occurrence of P . Then, we can compute
Occ(P, T ) by ﬁrst computing such a primary occurrence and enumerating the
occurrences of X in the derivation tree.
Formally, we deﬁne the primary occurrences of P as follows.
Definition 4 (The set of primary occurrences of P ). For a string P with
|P | > 1 and an integer 1 ≤ j < |P |, we define pOcc S (P, j) and pOcc S (P ) as
follows:
pOcc S (P, j) = {(X, |X.left| − j + 1) | X ∈ V,
P [..j] is a suffix of X.left, P [j + 1..] is a prefix of X.right},
[
pOcc S (P, j),
pOcc S (P ) =
1≤j<|P |

We call each element of pOcc S (P ) a primary occurrence of P .
The set Occ(P, T ) of occurrences of P in T is represented by pOcc S (P ) as follows.
Observation 1 For any string P ,
(
{j + k − 1 | (X, j) ∈ pOcc S (P ), k ∈ vOcc(X, S)}
Occ(P, T ) =
vOcc(X, S)((X → P ) ∈ D)
15

if |P | > 1,
if |P | = 1.

By Observation 1, the task is to compute pOcc S (P ) and vOcc(X, S) eﬃciently. Note that vOcc(X, S) can be computed in O(|vOcc(X, S)|h) time by
traversing the DAG in a reversed direction (i.e., using parents(X) function recursively) from X to the source, where h is the height of the derivation tree of
S. Hence, in what follows, we focus on how to compute pOcc S (P ) for a string P
with |P | > 1. In order to compute pOcc S (P, j), we use a data structure to solve
the following problem:
Problem 1 (Two-Dimensional Orthogonal Range Reporting Problem). Let X and
Y denote subsets of two ordered sets, and let R ⊆ X × Y be a set of points on
the two-dimensional plane, where |X |, |Y| ∈ O(|R|). A data structure for this
problem supports a query report R (x1 , x2 , y1 , y2 ); given a rectangle (x1 , x2 , y1 , y2 )
with x1 , x2 ∈ X and y1 , y2 ∈ Y, returns {(x, y) ∈ R | x1 ≤ x ≤ x2 , y1 ≤ y ≤ y2 }.
Data structures for Problem 1 are widely studied in computational geometry.
There is even a dynamic variant, which we ﬁnally use for our dynamic index in
Section 4.4. Until then, we just use any static data structure that occupies O(|R|)
space and supports queries in O(q̂|R| + q|R| qocc) time with q̂|R| = O(log |R|),
where qocc is the number of points to report.
Now, given an SLP S, we consider a two-dimensional plane deﬁned by X =
{X.leftR | X ∈ V} and Y = {X.right | X ∈ V}, where elements in X and Y are
sorted by lexicographic order. Then consider a set of points R = {(X.leftR , X.right) |
(P,j)
(P,j)
X ∈ V}. For a string P and an integer 1 ≤ j < |P |, let y1
(resp. y2 ) denote
the lexicographically smallest (resp. largest) element in Y that has P [j + 1..] as
a preﬁx. If there is no such element, it just returns NIL and we can immediately
(P,j)
(P,j)
know that pOcc S (P, j) = ∅. We also deﬁne x1
and x2
in a similar way
(P,j)
(P,j)
over X , i.e., x1
(resp. x2 ) is the lexicographically smallest (resp. largest)
element in X that has P [..j]R as a preﬁx. Then, pOcc S (P, j) can be computed
(P,j)
(P,j) (P,j) (P,j)
by a query report R (x1 , x2 , y1 , y2 ). See also Example 5.
Example 5 (SLP). Let S be the SLP of Example 2. Then,
X = {x1 , x4 , x2 , x8 , x5 , x9 , x6 , x10 , x11 , x3 , x7 },
Y = {y1 , y8 , y2 , y7 , y9 , y3 , y4 , y5 , y6 , y10 , y11 },

where xi = val (Xi )R , yi = val (Xi ) for any Xi ∈ V. Given a pattern P = BCAB,
then pOcc S (P, 1) = {(X6 , 3), (X11 , 10)}, pOcc S (P, 2) = {(X9 , 1)}, pOcc S (P, 3) =
φ, vOcc S (X6 , S) = {1, 11}, vOcc S (X9 , S) = {7} and vOcc S (X11 , S) = {1}.
Hence pOcc S (P ) = {(X6 , 3), (X11 , 10), (X9 , 1)} and Occ(P, T ) = {3, 7, 10, 13}.
See also Fig. 3.
We can get the following result:
Lemma 10. For an SLP S of size n, there exists a data structure of size O(n)
that computes, given a string P , pOcc S (P ) in O(|P |(h+|P |) log n+qn |pOcc S (P )|)
time.
16

(P,j)

(P,j)

(P,j)

Proof. For every 1 ≤ j < |P |, we compute pOcc S (P, j) by report R (x1 , x2 , y1
(P,j)
(P,j)
We can compute y1
and y2
in O((h+|P |) log n) time by binary search on Y,
where each comparison takes O(h+ |P |) time for expanding the ﬁrst O(|P |) char(P,j)
(P,j)
acters of variables subjected to comparison. In a similar way, x1
and x2
can be computed in O((h + |P |) log n) time. Thus, the total time complexity is
O(|P |((h+|P |) log n+q̂n )+qn |pOcc S (P )|) = O(|P |(h+|P |) log n+qn |pOcc S (P )|).
⊓
⊔
4.2

Static Index for Run-length ACFG

In this subsection, we extend the idea for the SLP index described in Section 4.1
to run-length ACFGs. Consider occurrences of string P with |P | > 1 in runlength ACFG G = (Σ, V, D, S) generating string T . The diﬀerence from SLPs is
that we have to deal with occurrences of P that are covered by a node labeled
with e → êd but not covered by any single child of the node in the derivation
tree. In such a case, there must exist P = P1 P2 with 1 ≤ |P1 | < |P | such that
P1 is a suﬃx of e.left = val + (ê) and P2 is a preﬁx of e.right = val + (êd−1 ). Let
j = |val (ê)|−|P1 |+1 be a position in val + (êd ) where P occurs, then P also occurs
at j +c|val (ê)| in val + (êd ) for every positive integer c with j +c|val (ê)|+|P |−1 ≤
|val + (êd )|. Remarking that we apply Deﬁnition 4 of primary occurrences to runlength ACFGs as they are, we formalize our observation to compute Occ(P, T )
as follows:
Observation 2 For any string P with |P | > 1, Occ(P, T ) = {j + k + c − 1 |
(e, i) ∈ pOcc G (P ), c ∈ {0} ∪ Run G (e, j, |P |), k ∈ vOcc(e, S)}, where
(
{c|val (ê)| | 1 ≤ c, j + c|val (ê)| + |P | − 1 ≤ |val + (êd )|} if e → êd ,
Run G (e, j, |P |) =
∅
otherwise.
By the above observation, we can get the same result for a run-length ACFG as
for an SLP in Lemma 10.
4.3

Static Index for Signature Encoding

We can apply the result of Section 4.2 to signature encodings because signature
encodings are run-length ACFGs, i.e., we can compute Occ(P, T ) by querying
(P,j)
(P,j) (P,j) (P,j)
report R (x1 , x2 , y1 , y2 ) for “every” 1 ≤ j < |P |. However, the properties of signature encodings allow us to speed up pattern matching as summarized
(P,j)
(P,j) (P,j)
in the following two ideas: (1) We can eﬃciently compute x1 , x2 , y1
and
(P,j)
y2
using LCE queries in compressed space (Lemma 11). (2) We can reduce
the number of report R queries from O(|P |) to O(log |P | log∗ M ) by using the
property of the common sequence of P (Lemma 12).
Lemma 11. Assume that we have the DAG for a signature encoding G = (Σ, V, D, S)
of size w and X and Y of G. Given a signature id (P ) ∈ V for a string P and
(P,j)
(P,j) (P,j)
(P,j)
in O(log w(log N +
and y2
an integer j, we can compute x1 , x2 , y1
∗
log |P | log M )) time.
17

(P,j)

, y2

).

(P,j)

(P,j)

Proof. By Lemma 8 and Fact 1, we can compute x1
and x2
on X by binary
(P,j)
∗
search in O(log w(log N + log |P | log M )) time. Similarly, we can compute y1
(P,j)
and y2
in the same time.
⊓
⊔

Lemma 12. Let P be a string with |P | > 1. If |Pow P
0 | = 1, then pOcc G (P ) =
S
pOcc
pOcc G (P, 1). If |Pow P
|
>
1,
then
pOcc
(P
)
=
G (P, j), where u is the
0
G
j∈P
+
common sequence of P and P = {|val (u[1..i])| | 1 ≤ i < |u|, u[i] 6= u[i + 1]}.

|P |
Proof. If |Pow P
for some character a ∈ Σ. In this case, P
0 | = 1, then P = a
must be contained in a node labeled with a signature e → êd such that ê → a
and d ≥ |P |. Hence, all primary occurrences of P can be found by pOcc G (P, 1).
If |Pow P
0 | > 1, we consider the common sequence u of P . Recall that u
occurs at position
j in e for any (e, j) ∈ pOcc(P ) by Lemma 4. Hence at least
S
pOcc G (P ) = i∈P ′ pOcc G (P, i) holds, where P ′ = {|val + (u[1])|, . . . , |val + (u[..|u|−
1])|}. Moreover, we show that pOcc G (P, i) = ∅ for any i ∈ P ′ with u[i] = u[i + 1].
Note that u[i] and u[i + 1] are encoded into the same signature in the derivation
tree of e, and that the parent of two nodes corresponding to u[i] and u[i + 1] has
a signature e′ in the form e′ → u[i]d . Now assume for the sake of contradiction
that e = e′ . By the deﬁnition of the primary occurrences, i = 1 must hold, and
|P |
hence, Shrink P
, which contradicts
0 [1] = u[1] ∈ Σ. This means that P = u[1]
|Pow P
|
>
1.
Therefore
the
statement
holds.
⊓
⊔
0

Using Lemmas 2, 7, 11 and 12, we get the following lemma:
′
Lemma 13. For a signature encoding G, represented by H(fA , fA
), of size w
which generates a text T of length N , there exists a data structure of size O(w)
that computes, given a string P , pOcc G (P ) in O(|P |fA +log w log |P | log∗ M (log N +
log |P | log∗ M ) + qw |pOcc S (P )|) time.

Proof. We focus on the case |Pow P
0 | > 1 as the other case is easier to be solved.
We ﬁrst compute the common sequence of P in O(|P |fA ) time. Taking P in
Lemma 12, we recall that |P| = O(log |P | log∗ M ) by Lemma 4. Then, in light
of Lemma 12, pOcc G (P ) can be obtained by |P| = O(log |P | log∗ M ) range
reporting queries. For each query, we spend O(log w(log N + log |P | log∗ M ))
(P,j)
(P,j) (P,j)
(P,j)
time to compute x1 , x2 , y1
and y2
by Lemma 11. Hence, the total time complexity is O(|P |fA + log |P | log∗ M (log w(log N + log |P | log∗ M ) +
q̂w ) + qw |pOcc S (P )|) = O(|P |fA + log w log |P | log∗ M (log N + log |P | log∗ M ) +
qw |pOcc S (P )|).
⊓
⊔
4.4

Dynamic Index for Signature Encoding

In order to dynamize our static index in the previous subsection, we consider a
data structure for “dynamic” two-dimensional orthogonal range reporting that
can support the following update operations:
– insert R (p, xpred , ypred ): given a point p = (x, y), xpred = max{x′ ∈ X | x′ ≤
x} and ypred = max{y ′ ∈ Y | y ′ ≤ y}, insert p to R and update X and Y
accordingly.
18

– delete R (p): given a point p = (x, y) ∈ R, delete p from R and update X and
Y accordingly.
We use the following data structure:
Lemma 14 ([7]). There exists a data structure that supports report R (x1 , x2 , y1 , y2 )
in O(log |R| + occ(log |R|/ log log |R|)) time, and insert R (p, i, j), delete R (p) in
amortized O(log |R|) time, where occ is the number of the elements to output.
This structure uses O(|R|) space. 4
Now we are ready to prove Theorem 1.
′
Proof (Proof of Theorem 1). Our index consists of H(fA , fA
) and a dynamic
range reporting data structure Λ of Lemma 14 whose R is maintained as they
are deﬁned in the static version. We maintain X and Y in two ways; self-balancing
binary search trees for binary search, and Dietz and Sleator’s data structures
for order maintenance. Then, primary occurrences of P can be computed as
described in Lemma 13. Adding the O(occ log N ) term for computing all pattern
occurrences from primary occurrences, we get the time complexity for pattern
matching in the statement. Concerning the update of our index, we described
how to update H after INSERT and DELETE in Lemma 9. What remains is to
show how to update Λ when a signature is inserted into or deleted from V. When
a signature e is deleted from V, we ﬁrst locate e.leftR on X and e.right on Y,
and then execute delete R (e.leftR , e.right). When a signature e is inserted into V,
we ﬁrst locate xpred = max{x′ ∈ X | x′ ≤ e.leftR } on X and ypred = max{y ′ ∈
Y | y ′ ≤ e.right} on Y, and then execute insert R ((e.leftR , e.right), xpred , ypred ).
The locating can be done by binary search on X and Y in O(log w log N log∗ M )
time as Lemma 11. In a single INSERT (i, Y ) or DELETE (i, y) operation, O(y +
log N log∗ M ) signatures are inserted into or deleted from V, where |Y | = y.
Hence we get Theorem 1.
⊓
⊔

5

Applications

In this section, we present a number of applications of the data structures of
Sections 3 and 4. Theorems 3 and 4 are applications to text compression.
Theorem 3. Given a string T of length N , we can compute the LZ77 Factoriza′
tion of T in O(N fA +z log w log3 N (log∗ N )2 ) time and O(w+fA
) working space
′
using H(fA , fA
) for a signature encoding of size w which generates T , where z
is the size of the LZ77 factorization of T and w = O(z log N log∗ N ).
4

The original problem considers a real plane in the paper [7], however, his solution
only need to compare any two elements in R in constant time. Hence his solution
can apply to our range reporting problem by maintains X and Y using the data
structure of order maintenance problem proposed by Dietz and Sleator [9], which
enables us to compare any two elements in a list L and insert/delete an element
to/from L in constant time.

19

′
Theorem 4. (1) Given an H(fA , fA
) for a signature encoding G = (Σ, V, D, S)
of size w which generates T , we can compute an SLP S of size O(w log |T |) generating T in O(w log |T |) time. (2) Let us conduct a single INSERT or DELETE
operation on the string T generated by the SLP of (1). Let y be the length of the
substring to be inserted or deleted, and let T ′ be the resulting string. During the
above operation on the string, we can update, in O((y + log |T ′ | log∗ M )(fA +
log |T ′ |)) time, the SLP of (1) to an SLP S ′ of size O(w′ log |T ′ |) which generates T ′ , where M is the maximum length of the dynamic text, w′ is the size of
updated G which generates T ′ .

Theorems 5-9 are applications to compressed string processing (CSP), where
the task is to process a given compressed representation of string(s) without
explicit decompression.
Theorem 5. Given an SLP S of size n generating a string of length N , we can
construct, in O(n log log n log N log∗ N ) time, a data structure which occupies
O(n log N log∗ N ) space and supports LCP(Xi , Xj ) and LCS(Xi , Xj ) queries for
variables Xi , Xj in O(log N ) time. The LCP(Xi , Xj ) and LCS(Xi , Xj ) query
times can be improved to O(1) using O(n log n log N log∗ N ) preprocessing time.
Theorem 6. Given an SLP S of size n generating a string T of length N ,
there is a data structure which occupies O(w + n) space and supports queries
LCE(Xi , Xj , a, b) for variables Xi , Xj , 1 ≤ a ≤ |Xi | and 1 ≤ b ≤ |Xj | in
O(log N + log ℓ log∗ N ) time, where w = O(z log N log∗ N ). The data structure can be constructed in O(n log log n log N log∗ N ) preprocessing time and
O(n log∗ N + w) working space, where z ≤ n is the size of the LZ77 factorization
of T and ℓ is the answer of LCE query.
Let h be the height of the derivation tree of a given SLP S. Note that h ≥
log N . Matsubara et al. [21] showed an O(nh(n+ h log N ))-time O(n(n+ log N ))space algorithm to compute an O(n log N )-size representation of all palindromes
in the string. Their algorithm uses a data structure which supports in O(h2 )
time, LCE queries of a special form LCE(Xi , Xj , 1, pj ) [23]. This data structure
takes O(n2 ) space and can be constructed in O(n2 h) time [19]. Using Theorem 6,
we obtain a faster algorithm, as follows:
Theorem 7. Given an SLP of size n generating a string of length N , we can
compute an O(n log N )-size representation of all palindromes in the string in
O(n log2 N log∗ N ) time and O(n log∗ N + w) space.
A non-empty string s is called a Lyndon word if s is the lexicographically
smallest suﬃx of s. The Lyndon factorization of a non-empty string w is a
sequence of pairs (|fi |, pi ) where each fi is a Lyndon word and pi is a positive
pm
integer such that w = f1p1 · · · fm
and fi−1 is lexicographically smaller than fi
for all 1 ≤ i < m. I et al. [14] proposed a Lyndon factorization algorithm running
in O(nh(n + log n log N )) time and O(n2 ) space. Their algorithm use the LCE
data structure on SLPs [16] which requires O(n2 h) preprocessing time, O(n2 )
working space, and O(h log N ) time for LCE queries. We can obtain a faster
algorithm using Theorem 6.
20

Theorem 8. Given an SLP of size n generating a string of length N , we can
compute the Lyndon factorization of the string in O(n(n + log n log N log∗ N ))
time and O(n2 + z log N log∗ N )) space.
We can also solve the grammar compressed dictionary matching problem [17]
with our data structures. We preprocess an input dictionary SLP (DSLP) hS, mi
with n productions that represent m patterns. Given an uncompressed text T ,
the task is to output all occurrences of the patterns in T .
Theorem 9. Given a DSLP hS, mi of size n that represents a dictionary ΠhS,mi
for m patterns of total length N , we can preprocess the DSLP in O((n log log n +
m log m) log N log∗ N ) time and O(n log N log∗ N ) space so that, given any text
T in a streaming fashion, we can detect all occ occurrences of the patterns in T
in O(|T | log m log N log∗ N + occ) time.
It was shown in [17] that we can construct in O(n4 log n) time a data structure
of size O(n2 log N ) which ﬁnds all occurrences of the patterns in T in O(|T |(h +
m)) time, where h is the height of the derivation tree of DSLP hS, mi. Note
that our data structure of Theorem 9 is always smaller, and runs faster when
h = ω(log m log N log∗ N ).
Acknowledgments. We would like to thank Pawel Gawrychowski for drawing
our attention to the work by Alstrup et al. [2,3] and for fruitful discussions.

References
1. Agarwal, P.K., Arge, L., Govindarajan, S., Yang, J., Yi, K.: Efficient external
memory structures for range-aggregate queries. Comput. Geom. 46(3), 358–370
(2013), http://dx.doi.org/10.1016/j.comgeo.2012.10.003
2. Alstrup, S., Brodal, G.S., Rauhe, T.: Dynamic pattern matching. Tech. rep., Department of Computer Science, University of Copenhagen (1998)
3. Alstrup, S., Brodal, G.S., Rauhe, T.: Pattern matching in dynamic texts. In: Proc.
SODA 2000. pp. 819–828 (2000)
4. Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65(1), 38–72 (2002),
http://dx.doi.org/10.1006/jcss.2002.1822
5. Bille, P., Cording, P.H., Gørtz, I.L., Sach, B., Vildhøj, H.W., Vind, S.: Fingerprints
in compressed strings. In: Proc. WADS 2013. pp. 146–157 (2013)
6. Bille, P., Christiansen, A.R., Cording, P.H., Gørtz, I.L.: Finger search, random
access, and longest common extensions in grammar-compressed strings. CoRR
abs/1507.02853 (2015)
7. Blelloch, G.E.: Space-efficient dynamic orthogonal point location, segment intersection, and range reporting. In: Teng, S.H. (ed.) SODA. pp. 894–903. SIAM (2008)
8. Claude, F., Navarro, G.: Self-indexed grammar-based compression. Fundamenta
Informaticae 111(3), 313–337 (2011)
9. Dietz, P.F., Sleator, D.D.: Two algorithms for maintaining order in a list. In:
Aho, A.V. (ed.) Proceedings of the 19th Annual ACM Symposium on Theory
of Computing, 1987, New York, New York, USA. pp. 365–372. ACM (1987),
http://doi.acm.org/10.1145/28395.28434

21

10. Fischer, J., Gagie, T., Gawrychowski, P., Kociumaka, T.: Approximating LZ77 via
small-space multiple-pattern matching. In: ESA 2015. pp. 533–544 (2015)
11. Goto, K., Maruyama, S., Inenaga, S., Bannai, H., Sakamoto, H., Takeda, M.: Restructuring compressed texts without explicit decompression. CoRR abs/1107.2729
(2011)
12. Han, Y.: Deterministic sorting in O(n log log n) time and linear space. Proc. STOC
2002 pp. 602–608 (2002)
13. Hon, W., Lam, T.W., Sadakane, K., Sung, W., Yiu, S.: Compressed index for
dynamic text. In: DCC 2004. pp. 102–111 (2004)
14. I, T., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Faster Lyndon factorization algorithms for SLP and LZ78 compressed text. In: Proc. SPIRE. pp. 174–185
(2013)
15. I, T., Matsubara, W., Shimohira, K., Inenaga, S., Bannai, H., Takeda, M., Narisawa, K., Shinohara, A.: Detecting regularities on grammar-compressed strings.
Inf. Comput. 240, 74–89 (2015)
16. I, T., Matsubara, W., Shimohira, K., Inenaga, S., Bannai, H., Takeda, M., Narisawa, K., Shinohara, A.: Detecting regularities on grammar-compressed strings.
Inf. Comput. 240, 74–89 (2015), http://dx.doi.org/10.1016/j.ic.2014.09.009
17. I, T., Nishimoto, T., Inenaga, S., Bannai, H., Takeda, M.: Compressed automata for dictionary matching. Theor. Comput. Sci. 578, 30–41 (2015),
http://dx.doi.org/10.1016/j.tcs.2015.01.019
18. Kieffer, J.C., Yang, E.: Grammar-based codes: A new class of universal lossless
source codes. IEEE Transactions on Information Theory 46(3), 737–754 (2000)
19. Lifshits, Y.: Processing compressed texts: A tractability border. In: Proc. CPM
2007. LNCS, vol. 4580, pp. 228–240 (2007)
20. Maruyama, S., Nakahara, M., Kishiue, N., Sakamoto, H.: Esp-index: A compressed
index based on edit-sensitive parsing. J. Discrete Algorithms 18, 100–112 (2013)
21. Matsubara, W., Inenaga, S., Ishino, A., Shinohara, A., Nakamura, T., Hashimoto,
K.: Efficient algorithms to compute compressed longest common substrings and
compressed palindromes. Theor. Comput. Sci. 410(8–10), 900–913 (2009)
22. Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica 17(2), 183–198 (1997)
23. Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm
for strings in terms of straight-line programs. In: Proc. CPM 1997. pp. 1–11 (1997)
24. Munro, J.I., Nekrich, Y., Vitter, J.S.: Dynamic data structures for document collections and graphs. CoRR abs/1503.05977 (2015)
25. Policriti, A., Prezza, N.: Fast online Lempel-Ziv factorization in compressed space.
In: SPIRE 2015. pp. 13–20 (2015)
26. Sahinalp, S.C., Vishkin, U.: Data compression using locally consistent parsing.
TechnicM report, University of Maryland Department of Computer Science (1995)
27. Sahinalp, S.C., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm (extended abstract). In: FOCS. pp. 320–328. IEEE
Computer Society (1996)
28. Sakamoto, H., Maruyama, S., Kida, T., Shimozono, S.: A space-saving approximation algorithm for grammar-based compression. IEICE Transactions 92-D(2),
158–165 (2009)
29. Salson, M., Lecroq, T., Léonard, M., Mouchard, L.: Dynamic extended suffix arrays.
J. Discrete Algorithms 8(2), 241–257 (2010)
30. Takabatake, Y., Tabei, Y., Sakamoto, H.: Improved esp-index: A practical selfindex for highly repetitive texts. In: Proc. SEA 2014. pp. 338–350 (2014)

22

31. Takabatake, Y., Tabei, Y., Sakamoto, H.: Online self-indexed grammar compression. In: SPIRE 2015. pp. 258–269 (2015)
32. Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE
Transactions on Information Theory IT-23(3), 337–349 (1977)

23

pow2T=!

17!

shrink2T=!

16!
15!
12!

pow1T=!
shrink1T=! 9!

13!
9!

8!

14!

10! 10! 10! 10! 10! 10! 10! 11!

8!

10!

pow0T=! 7! 5! 6! 7! 5! 6! 5! 6! 5! 6! 5! 6! 5! 6! 5! 6! 5! 6! 5! 6! 5! 6!

4!

shrink0T=! 3! 1! 2! 3! 1! 2! 1! 2! 1! 2! 1! 2! 1! 2! 1! 2! 1! 2! 1! 2! 1! 2! 3! 3! 3! 3!
T =!

C! A! B! C! A! B! A! B! A! B! A! B! A! B! A! B! A! B! A! B! A! B! C! C! C! C!

17!
16!
15!
12!

14!
13!
11!

9!
8!

10!
4!

7! 5! 6!
3! 1! 2!
Fig. 1. The derivation tree of S (left) and the DAG for G (right) of Example 3. In
the DAG, the black and red arrows represent e → el er and e → êk respectively. In
Example 4, T is encoded by signature encoding. In the derivation tree of S, the dotted
boxes represent the blocks created by the Eblock function.

24

S!
(1)!

XShrink2P!
XPow1P!
XShrink1P!
XPow0P!
XShrink0P!
T=!

L

P!

R!

(2)!
shrink1T = !
pow1T = !
shrink1T = !
pow0T = !
shrink0T = !
T=!

XShrink2P!
shrink2T[..c^!2]!
P!
T
L1
pow1 [..c1]!
R1P!
T
^! 1P!
^!
^!
shrink1 [..c1]!
R
L1P!
T
P!
pow0 [..c0]!
R0P!
L0
T
P!
^!
^! 0P!
^!
shrink0 [..c0]! L0
R
L
P!

R!

S!
(3)!

L

P!

C

P!

R!

id(s3)!

(4)!
subtree X !

s1
Uniq(s1) !

s2!
Uniq(s2) !

Fig. 2. Abstract images of consistent signatures of substring P of text T , on the
derivation trees of the signature encoding of T . Gray rectangles in Figures (1)-(3)
represent consistent signature sequences for occurrences of P . (1) Each XShrink P
t and
T
T
XPow P
t occur on substring P in shrink t and Pow t , respectively, where T = LP R. (2)
P P P
P P P P P
The substring P can be represented by L̂P
0 L0 L̂1 L1 XShrink 2 R1 R̂1 R0 R̂0 . (3) There
exist common signatures on every substring P in the derivation tree. (4) The derivation
tree of id (s3 ) and the subtree X in the proof of Lemma 6.

25

"!
X11!
X10!
X6!
X11!
X6!
X5!
X4!
X3!
X7!
X9!
X10!
X7!
X2! X8! X5!
X8!
X9!
X4!
X1!
X1 X4 X2 X8 X5 X9 X6 X10 X11 X3 X7!

!!

Fig. 3. The grid represents the relation between X , Y and R of Example 5. The red
(P,1)
(P,1)
(P,1)
(P,1)
(P,1)
(P,1)
=
= x2 , x2
), where x1
, y2
rectangle is a query rectangle (x1 , x2 , y1
(P,1)
(P,1)
(P,1)
(P,1)
(P,1)
(P,1)
x11 , y1
= y5 and y2
= y11 . Therefore, report R (x1 , x2 , y1
, y2
) =
{X6 , X11 }.

26

A

Appendix : Theorem 2

A.1

Proof of Theorem 2 (1)

H(log w, w) construction in O(N ) time and space. Our algorithm computes signatures level by level, i.e., constructs incrementally Shrink T0 , Pow T0 ,
. . . , Shrink Th , Pow Th . For each level, we determine signatures by sorting signature blocks (or run-length encoded signatures) to which we give signatures. The
following two lemmas describe the procedure.
Lemma 15. Given Eblock (Pow Tt−1 ) for 0 < t ≤ h, we can compute Shrink Tt in
O((b−a)+|Pow Tt−1 |) time and space, where b is the maximum integer in Pow Tt−1
and a is the minimum integer in Pow Tt−1 .
Proof. Since we assign signatures to signature blocks and run-length signatures
in the derivation tree of S in the order they appear in the signature encoding.
Pow Tt−1 [i]−a ﬁts in an entry of a bucket of size b−a for each element of Pow Tt−1 [i]
of Pow Tt−1 . Also, the length of each block is at most four. Hence we can sort all
the blocks of Eblock (Pow Tt−1 ) by bucket sort in O((b − a) + |Pow Tt−1 |) time and
space. Since Sig is an injection and since we process the levels in increasing order,
for any two diﬀerent levels 0 ≤ t′ < t ≤ h, no elements of Shrink Tt−1 appear in
Shrink Tt′ −1 , and hence no elements of Pow Tt−1 appear in Pow Tt′ −1 . Thus, we can
determine a new signature for each block in Eblock (Pow Tt−1 ), without searching
existing signatures in the lower levels. This completes the proof.
Lemma 16. Given Epow (Shrink Tt ), we can compute Pow Tt in O(x + (b − a) +
|Epow (Shrink Tt )|) time and space, where x is the maximum length of runs in
Epow (Shrink Tt ), b is the maximum integer in Pow Tt−1 , and a is the minimum
integer in Pow Tt−1 .
Proof. We ﬁrst sort all the elements of Epow (Shrink Tt ) by bucket sort in O(b −
a+|Epow (Shrink Tt )|) time and space, ignoring the powers of runs. Then, for each
integer r appearing in Shrink Tt , we sort the runs of r’s by bucket sort with a
bucket of size x. This takes a total of O(x + |Epow (Shrink Tt )|) time and space for
all integers appearing in Shrink Tt . The rest is the same as the proof of Lemma 15.
The next lemma shows how to construct H(log w, w) from a sorted assignment set D of G.
Lemma 17. Given a sorted assignment set D of G, we can construct H(log w, w)
of G in O(|V|) time.
Proof. Recall that H consists of A and DAG B. Clearly, given a sorted assignment set D, we can construct B in linear time and space. Also, we can construct,
in linear time and space, a balanced search tree for A from D. Hence Lemma 17
holds.
We are ready to prove the theorem.
27

Proof. In the derivation tree of id (T ), since the number of nodes in some level
is halved when going up two levels higher, every node of Since the size of the
derivation tree of id (T ) is O(N ), by Lemmas 1, 15, and 16, we can compute
id (T ) and a sorted assignment set D of G in O(N ) time and space. Finally, by
Lemma 17, we can get H(log w, w) for G in O(N ) time.
′
′
H(fA , fA
) construction in O(N fA ) time and O(fA
+w) working space.

Proof. Note that we can naively compute id (T ) for a given string T in O(N fA )
time and O(N ) working space. In order to reduce the working space, we consider
factorizing T into blocks of size B and processing them incrementally: Starting
∗
with the empty signature encoding G, we can compute id (T ) in O( N
B fA (log N log M +
′
B)) time and O(w + B + fA ) working space by using INSERT (T [(i − 1)B +
1..iB], (i − 1)B + 1) for i = 1, . . . , N
B in increasing order. Hence our proof is
ﬁnished by choosing B = log N log∗ M .
A.2

Proof of Theorem 2 (2)

′
Proof. Consider H(fA , fA
) for an empty signature encodings G. If we can compute INSERT (Y, i) operation in O(fA log N log∗ M ) time, then Theorem 2 (2)
immediately holds by computing INSERT (fi , |f1 · · · fi−1 | + 1) for 1 ≤ i ≤ z
incrementally. By the proof of Lemma 9, we can compute INSERT (Y, i) for
a given Uniq(Y ) in O(fA log N log∗ M ) time. We can compute each Uniq(fi )
in O(log N log∗ M ) time by Lemma 7 because fi occurs previously in T when
|fi | > 1. Hence we get Theorem 2 (2).

Note that we can directly show Lemma 3 from the above proof because the size of
G increases O(log N log∗ M ) by Lemma 6, every time we do INSERT (fi , |f1 · · · fi−1 |+
1) for 1 ≤ i ≤ z.
A.3

Proof of Theorem 2 (3)

′
′
H(fA , fA
) construction in O(nfA log N log∗ M ) time and O(fA
+ w)
working space.
′
Proof. We can construct H(fA , fA
) by O(n) INSERT operations as the proof of
Theorem 2 (2).

H(log w, w) construction in O(n log log n log N log∗ M ) time and O(n log∗ M +
w) working space. In this section, we sometimes abbreviate val (X) as X for
val(X)
val(X)
X
X ∈ S. For example, Shrink X
and Pow t
t and Pow t represents Shrink t
respectively.
Our algorithm computes signatures level by level, i.e., constructs incremenXn
Xn
Xn
n
tally Shrink X
0 , Pow 0 , . . . , Shrink h , Pow h . Like the algorithm described in
Section A.1, we can create signatures by sorting blocks of signatures or runlength encoded signatures in the same level. The main diﬀerence is that we now
28

utilize the structure of the SLP, which allows us to do the task eﬃciently in
Xn
n
O(n log∗ M + w) working space. In particular, although |Shrink X
t |, |Pow t | =
∗
O(N ) for 0 ≤ t ≤ h, they can be represented in O(n log M ) space.
In so doing, we introduce some additional notations relating to XShrink P
t
and XPow P
t in Deﬁnition 3. By Lemma 4, for any string P = P1 P2 the following
equation holds:
(P1 ,P2 ) P2
ŷt
P1 (P1 ,P2 ) P2
yt zt
yt

P1
XShrink P
t = ŷt ẑt

XPow P
t =

for 0 < t ≤ hP ,

for 0 ≤ t < hP ,

where we deﬁne ŷtP and ytP for a string P as follows:
(
XShrink P
for 0 < t ≤ hP ,
t
P
ŷt =
ε
for t > hP ,
(
XPow P
for 0 ≤ t < hP ,
t
ytP =
ε
for t ≥ hP .
(val(X ),val(X ))

r
ℓ
For any variable Xi → Xℓ Xr , we denote ẑtXi = ẑt
(for 0 <
(val(Xℓ ),val(Xr ))
Xi
val(Xi )
val(Xi )
t ≤ h
) and zt = zt
(for 0 ≤ t < h
). Note that
|ztXi |, |ẑtXi | = O(log∗ N ) by Lemma 5. We can use ẑtX1 , . . . , ẑtXn (resp. ztX1 , . . . , ztXn )
n
n
as a compressed representation of XShrink X
(resp. XPow X
t
t ) based on the SLP:
Xn
Xn
n
n
Intuitively, ẑt (resp. zt ) covers the middle part of XShrink X
(resp. XPow X
t )
t
and the remaining part is recovered by investigating the left/right child recurn
sively (see also Figure. 4). Hence, with the DAG structure of the SLP, XShrink X
t
Xn
∗
and XPow t can be represented in O(n log M ) space.
P
P
P
P
P
In addition, we deﬁne ÂP
t , B̂t , At and Bt as follows: For 0 < t ≤ h , Ât
P
P
(resp. B̂t ) is a preﬁx (resp. suﬃx) of Shrink t which consists of signatures of
P
P
P
P
P
P
AP
t−1 Lt−1 (resp. Rt−1 Bt−1 ); and for 0 ≤ t < h , At (resp. Bt ) is a preﬁx (resp.
P
P P
suﬃx) of Pow t which consists of signatures of Ât L̂t (resp. R̂tP B̂tP ). By the deﬁP P
P
P P
P
P
P
nition, Shrink P
t = Ât XShrink t B̂t for 0 ≤ t ≤ h , and Pow t = At XPow t Bt
P
for 0 ≤ t < h . See Figure 5 for the illustration.
Xn Xn
n
n
Since Shrink X
= ÂX
for 0 < t ≤ hXn , we use Λ̂t =
t
t XShrink t B̂t
X1
Xn
Xn
Xn
n
(ẑt , . . . , ẑt , Ât , B̂t ) as a compressed representation of Shrink X
of size
t
∗
X1
Xn
Xn
Xn
O(n log M ). Similarly, for 0 ≤ t < h , we use Λt = (zt , . . . , zt , At , BtXn )
n
as a compressed representation of Pow X
of size O(n log∗ M ).
t
Our algorithm computes incrementally Λ0 , Λ̂1 , . . . , Λ̂hXn . Note that, given
n
Λ̂hXn , we can easily get Pow X
of size O(log∗ M ) in O(n log∗ M ) time, and
hXn
n
then id (val (Xn )) in O(log∗ M ) time from Pow X
. Hence, in the following three
hXn
lemmas, we show how to compute Λ0 , Λ̂1 , . . . , Λ̂hXn .

Lemma 18. Given an SLP of size n, we can compute Λ0 in O(n log log n log∗ M )
time and O(n log∗ M ) space.
Xi
i
Proof. We ﬁrst compute, for all variables Xi , Epow (XShrink X
0 ) if |Epow (XShrink 0 )| ≤
Xi
Xi
∆L + ∆R + 9, otherwise Epow (L̂0 ) and Epow (R̂0 ). The information can be

29

XPowtXn
ztXn
XPowtXn-1
ztXn-1
XPowtXn-3
ztXn-3

ztXn-5

XPowtXn-2
ztXn-2
XPowtXn-4
ztXn-4

XPowtXn-7
ztXn-7

ztXn-6
n
can be represented by ztX1 , . . . , ztXn .
Fig. 4. XPow X
t

computed in O(n log∗ M ) time and space in a bottom-up manner, i.e., by processℓ
ing variables in increasing order. For Xi → Xℓ Xr , if both |Epow (XShrink X
0 )|
Xr
and |Epow (XShrink 0 )| are no greater than ∆L + ∆R + 9, we can compute
∗
Xℓ
i
Epow (XShrink X
0 ) in O(log M ) time by naively concatenating Epow (XShrink 0 )
Xr
Xi
and Epow (XShrink 0 ). Otherwise |Epow (XShrink 0 )| > ∆L +∆R +9 must hold,
Xi
i
and Epow (L̂X
0 ) and Epow (R̂0 ) can be computed in O(1) time from the information for Xℓ and Xr .
The run-length encoded signatures represented by z0Xi can be obtained by
using the above information for Xℓ and Xr in O(log∗ M ) time: z0Xi is created over
Xℓ
ℓ
run-length encoded signatures Epow (XShrink X
0 ) (or Epow (R̂0 )) followed by
Xr
Xn
r
Epow (XShrink X
and B0Xn represents
0 ) (or Epow (R̂0 )). Also, by deﬁnition A0
Xn
Xn
Epow (L̂0 ) and Epow (R̂0 ), respectively.
Hence, we can compute in O(n log∗ M ) time O(n log∗ M ) run-length encoded
signatures to which we give signatures. We determine signatures by sorting the
run-length encoded signatures as Lemma 16. However, in contrast to Lemma 16,
we do not use bucket sort for sorting the powers of runs because the maximum length of runs could be as large as N and we cannot aﬀord O(N ) space
for buckets. Instead, we use the sorting algorithm of Han [12] which sorts x
integers in O(x log log x) time and O(x) space. Hence, we can compute Λ0 in
O(n log log n log∗ M ) time and O(n log∗ M ) space.
Lemma 19. Given Λ̂t , we can compute Λt in O(n log log n log∗ M ) time and
O(n log∗ M ) space.
Proof. The computation process is similar to that of Lemma 18, except that we
also use the information in Λ̂t .
30

^P
^P
ShrinkP2 =
A
XShrinkP2
B
2
2
P
P
P
P
Pow 1 =
A 1
L 1
R 1
BP1
^P L
^P
^P B
^P
ShrinkP1 = A
R
1
1
1
1
P
P
P
P
Pow 0 =A 0 L 0
R 0 BP0
^P
^P
ShrinkP0 = L
R
0
0
P
P
P
P P
Fig. 5. An abstract image of Shrink P
t and Pow t for a string P . For 0 ≤ t < h , At Lt
P
P
P P
(resp. RtP BtP ) is encoded into ÂP
(resp.
B̂
).
Similarly,
for
0
<
t
<
h
,
Â
L̂
(resp.
t+1
t+1
t
t
P
R̂tP B̂tP ) is encoded into AP
t (resp. Bt ).

Xi
i
We ﬁrst compute, for all variables Xi , Epow (XShrink X
t ) if |Epow (XShrink t )| ≤
Xi
Xi
∆L + ∆R + 9, otherwise Epow (L̂t ) and Epow (R̂t ). The information can be
computed in O(n log∗ M ) time and space in a bottom-up manner, i.e., by processℓ
ing variables in increasing order. For Xi → Xℓ Xr , if both |Epow (XShrink X
t )|
r
and |Epow (XShrink X
)|
are
no
greater
than
∆
+
∆
+
9,
we
can
compute
L
R
t
∗
Xℓ
i
Epow (XShrink X
0 ) in O(log M ) time by naively concatenating Epow (XShrink t ),
Xi
Xr
Xi
Epow (ẑt ) and Epow (XShrink t ). Otherwise |Epow (XShrink t )| > ∆L +∆R +9
Xi
i
must hold, and Epow (L̂X
0 ) and Epow (R̂0 ) can be computed in O(1) time from
Xi
Epow (ẑt ) and the information for Xℓ and Xr .
The run-length encoded signatures represented by ztXi can be obtained in
O(log∗ M ) time by using ẑtXi and the above information for Xℓ and Xr : ztXi is
created over run-length encoded signatures that are obtained by concatenating
Xℓ
Xi
Xr
Xr
ℓ
Epow (XShrink X
0 ) (or Epow (R̂0 )), zt and Epow (XShrink 0 ) (or Epow (R̂0 )).
Xn
Xn
Xn Xn
Xn Xn
Also, At and Bt represents Ât L̂t and R̂t B̂t , respectively.
Hence, we can compute in O(n log∗ M ) time O(n log∗ M ) run-length encoded
signatures to which we give signatures. We determine signatures in O(n log log n log∗ M )
time by sorting the run-length encoded signatures as Lemma 19.

Lemma 20. Given Λt , we can compute Λ̂t+1 in O(n log∗ M ) time and O(n log∗ M )
space.
Xi
for a variable Xi → Xℓ Xr , we need a signature
Proof. In order to compute ẑt+1
Xi
sequence on which ẑt+1 is created, as well as its context, i.e., ∆L signatures to
the left and ∆R to the right. To be precise, the needed signature sequence is
Xj
Xj
Xj
r
vtXℓ ztXi uX
of length
t , where ut (resp. vt ) denotes a preﬁx (resp. suﬃx) of yt
n
∆L + ∆R + 4 for any variable Xj (see also Figure 6). Also, we need At uX
and
t
Xn
Xn
Xn
vt Bt to create Ât+1 and B̂t+1 , respectively.
Note that by Deﬁnition 3, |ztX | > ∆L + ∆R + 9 if ztX 6= ε. Then, we can
i
compute uX
for all variables Xi in O(n log∗ M ) time and space by processing
t
i
ℓ
variables in increasing order on the basis of the following fact: uX
= uX
if
t
t

31

^ t+1Xi XShrinkt+1X
Shrinkt+1Xi = A
X
A
XPowtX
i
Powt = t-1Xi
vtX
^ Xi
Shrinkt+1Xi = A
t+1
PowtXi = AtXi

^zt+1Xi
ztXi

z^t+1Xi

XShrinkt+1X
XPowtX
vtX

^ t+1Xi
Shrinkt+1Xi = A
PowtXi = AtXi

XShrinkt+1Xr
XPowtXr
utXr

ztXi

^zt+1Xi
ztXi

^ Xi
B
t+1
BtXi

^B Xi
t+1
BtXi

^ Xi
B
t+1
BtXi

r
r
Fig. 6. Abstract images of the needed signature sequence vtXℓ ztXi uX
(vtXℓ and uX
t
t
Xi
are not shown when they are empty) for computing ẑt+1 in three situations: Top for
0 ≤ t < hXℓ , hXr ; middle for hXr ≤ t < hXℓ ; and bottom for hXℓ , hXr ≤ t < hXi .

Xi
i
ztXℓ 6= ε, otherwise uX
of length ∆L + ∆R + 4. Similarly vtXi
t is the preﬁx of zt
for all variables Xi can be computed in O(n log∗ M ) time and space.
Using utXi and vtXi for all variables Xi , we can obtain O(n log∗ M ) blocks of
signatures to which we give signatures. We determine signatures by sorting the
blocks by bucket sort as Lemma 15 in O(n log∗ M ) time.
Hence, we can compute Λ̂t+1 in O(n log∗ M ) time and O(n log∗ M ) space.

We are ready to prove the theorem.
Proof. Using Lemmas 18, 19 and 20, we can get Λ̂hXn in O(n log log n log N log∗ M )
time by computing Λ0 , Λ̂1 , . . . , Λ̂hXn incrementally. Note that during the computation we only have to keep Λt (or Λ̂t ) for the current t and the assignments of G.
Hence the working space is O(n log∗ M + w). By processing Λ̂hXn in O(n log∗ M )
time, we can get a sorted assignment set D of G of size O(w). Finally, we process
G in O(w) time and space to get H(log w, w) by Lemma 17.

B
B.1

Appendix: Applications
Proof of Theorem 3

For integers j, k with 1 ≤ j ≤ j + k − 1 ≤ N , let Fst(j, k) be the function which
returns the minimum integer i such that i < j and T [i..i + k − 1] = T [j..j + k − 1],
if it exists. Our algorithm is based on the following fact:
Fact 2 Let f1 , . . . , fz be the LZ77-Factorization of a string T . Given f1 , . . . , fi−1 ,
we can compute fi with O(log |fi |) calls of Fst(j, k) (by doubling the value of k,
followed by a binary search), where j = |f1 · · · fi−1 | + 1.
We explain how to support queries Fst (j, k) using the signature encoding.
We deﬁne e.min = min vOcc(e, S) + |e.left| for a signature e ∈ V with e → eℓ er
32

or e → êk . We also deﬁne FstOcc(P, i) for a string P and an integer i as follows:
FstOcc(P, i) = min{e.min | (e, i) ∈ pOcc G (P, i)}
Then Fst(j, k) can be represented by FstOcc(P, i) as follows:
Fst (j, k) = min{FstOcc(T [j..j + k − 1], i) − i | i ∈ {1, . . . , k − 1}
= min{FstOcc(T [j..j + k − 1], i) − i | i ∈ P},

where P is the set of integers in Lemma 12 with P = T [j..j + k − 1].
Recall that in Section 4.3 we considered the two-dimensional orthogonal
range reporting problem to enumerate pOcc G (P, i). Note that FstOcc(P, i) can
be obtained by taking (e, i) ∈ pOcc G (P, i) with e.min minimum. In order to compute FstOcc(P, i) eﬃciently instead of enumerating all elements in pOcc G (P, i),
we give every point corresponding to e the weight e.min and use the next data
structure to compute a point with the minimum weight in a given rectangle.
Lemma 21 ([1]). Consider n weighted points on a two-dimensional plane. There
exists a data structure which supports the query to return a point with the minimum weight in a given rectangle in O(log2 n) time, occupies O(n) space, and
requires O(n log n) time to construct.
Using Lemma 21, we get the following lemma.
Lemma 22. Given a signature encoding G = (Σ, V, D, S) of size w which generates T , we can construct a data structure of O(w) space in O(w log w log N log∗ N )
time to support queries Fst (j, k) in O(log w log k log∗ N (log N + log k log∗ N ))
time.
Proof. For construction, we ﬁrst compute e.min in O(w) time using the DAG
of G. Next, we prepare the plane deﬁned by the two ordered sets X and Y in
Section 4.3. This can be done in O(w log w log N log∗ N ) time by sorting elements
in X (and Y) by LCE algorithm (Lemma 8) and a standard comparison-based
sorting. Finally we build the data structure of Lemma 21 in O(w log w) time.
To support a query Fst(j, k), we ﬁrst compute Epow (Uniq(P )) with P =
T [j..j + k − 1] in O(log N + log k log∗ N ) time by Lemma 7, and then get P in
Lemma 12. Since |P| = O(log k log∗ M ) by Lemma 4, Fst (j, k) = min{FstOcc(P, i)−
i | i ∈ P} can be computed by answering FstOcc O(log k log∗ M ) times. For each
computation of FstOcc(P, i), we spend O(log w(log N + log k log∗ N )) time to
(P,j)
(P,j) (P,j)
(P,j)
compute x1 , x2 , y1
and y2
by Lemma 11, and O(log2 w) time to com(P,j)
(P,j) (P,j) (P,j)
pute a point with the minimum weight in the rectangle (x1 , x2 , y1 , y2 ).
∗
∗
2
Hence it takes O(log k log M (log w(log N +log k log N )+log w)) = O(log w log k log∗ N (log N +
log k log∗ N )) time in total.
We are ready to prove Theorem 3 holds.
Proof (Proof of Theorem 3). We ﬁrst compute the signature encoding of T in
′
O(|T |fA ) time and O(fA
+ w) working space by the algorithm of Theorem 2 (1).
33

q
o

n
log M log log w
′
, logloglogww
Using a data structure H(fA , fA
) achieving fA = O min loglog
log log M
′
time and fA
= O(w) space, the working space becomes O(w) space. Next we
compute the z factors of the LZ77-Factorization of T incrementally by using
Fact 2 and Lemma 22 in O(z log w log3 N (log∗ N )2 ) time. Therefore the statement holds.
B.2

Proof of Theorem 4

Proof of Theorem 4 (1)
Proof. For any signature e ∈ V such that e → eℓ er , we can easily translate e
to a production of SLPs because the assignment is a pair of signatures, like the
right-hand side of the production rules of SLPs. For any signature e ∈ V such
that e → êk , we can translate e to at most 2 log k production rules of SLPs: We
1
2
t
create t = ⌊log k⌋ variables which represent ê2 , ê2 , . . . , ê2 and concatenating
them according to the binary representation of k to make up k ê’s. Therefore we
can compute S in O(w log |T |) time.
Proof of Theorem 4 (2)
Proof. Note that the number of created or removed signatures in V is bounded
by O(y + log |T ′ | log∗ M ) by Lemma 6. For each of the removed signatures, we
remove the corresponding production from S. For each of created signatures,
we create the corresponding production and add it to S as in the proof of (1).
Therefore Theorem 4 holds.
⊓
⊔
B.3

Proof of Theorem 5

We use the following known result.
Lemma 23 ([2]). Using the DAG for a signature encoding G = (Σ, V, D, S),
we can support
– LCP (s1 , s2 ) in O(log |s1 | + log |s2 |) time,
– LCS (s1 , s2 ) in O((log |s1 | + log |s2 |) log∗ M ) time
where id (s1 ), id (s2 ) ∈ V.
Proof. We compute LCP (s1 , s2 ) by LCE (s1 , s2 , 1, 1), namely, we use the algorithm of Lemma 8. Let P denote the longest common preﬁx of s1 and s2 . We use
the notation ÂP deﬁned in Section A.3. There exists a signature sequence v =
P
P
P
P P
ÂP
hP XShrink hP RhP −1 R̂hP −1 · · · R0 R̂0 that occurs at position 1 in id (s1 ) and
id (s2 ) by a similar argument of Lemma 4. Since |Epow (v)| = O(log |P |+log∗ M ),
we can compute LCP (s1 , s2 ) in O(log |s1 | + log |s2 |) time. Similarly, we can compute LCS (s1 , s2 ) in O((log |s1 | + log |s2 |) log∗ M ) time. More detailed proofs can
be found at [2].
⊓
⊔
34

To use Lemma 23 for id (val (X1 )), . . . , id (val (Xn )), we show the following
lemma.
Lemma 24. Given an SLP S, we can compute id (val (X1 )), . . . , id (val (Xn )) in
O(n log log n log N log∗ N ) time and O(n log N log∗ N ) space.
Proof. Recall that the algorithm of Theorem 2 (3) computes id (val (Xn )) in
O(n log log n log N log∗ N ) time. We can modify the algorithm to compute id (val (X1 )), . . . , id (val (Xn ))
X
X
X
without changing the time complexity: We just compute AX
t , Ât , Bt and B̂t
∗
for “all” X ∈ S, not only for Xn . Since the total size is O(n log N log N ),
Lemma 24 holds.
We are ready to prove Theorem 5.
Proof. The ﬁrst result immediately follows from Lemma 23 and 24. To speedup query times for LCP and LCS, We sort variables in lexicographical order in
O(n log n log N ) time by LCP query and a standard comparison-based sorting.
Constant-time LCP queries are then possible by using a constant-time RMQ data
structure [33] on the sequence of the lcp values. LCS queries can be supported
similarly.
⊓
⊔
B.4

Proof of Theorem 6

Proof. We can compute H(log w, w) for a signature encoding G = (Σ, V, D, S)
of size w representing T in O(n log log n log N log∗ N ) time and O(n log∗ M + w)
working space using Theorem 2, where w = O(z log N log∗ N ). Notice that each
variable of the SLP appears at least once in the derivation tree of Tn of the last
variable Xn representing the string T . Hence, if we store an occurrence of each
variable Xi in Tn and |val (Xi )|, we can reduce any LCE query on two variables
to an LCE query on two positions of val (Xn ) = T . In so doing, for all 1 ≤ i ≤ n
we ﬁrst compute |val (Xi )| and then compute the leftmost occurrence ℓi of Xi in
Tn , spending O(n) total time and space. By Lemma 8, each LCE query can be
supported in O(log N + log ℓ log∗ N ) time. Since z ≤ n [34], the total preprocessing time is O(n log log n log N log∗ N ) and working space is O(n log∗ M + w). ⊓
⊔
B.5

Proof of Theorem 7

Proof. For a given SLP of size n representing a string of length N , let P (n, N ),
S(n, N ), and E(n, N ) be the preprocessing time and space requirement for an
LCE data structure on SLP variables, and each LCE query time, respectively.
Matsubara et al. [21] showed that we can compute an O(n log N )-size representation of all palindromes in the string in O(P (n, N ) + E(n, N ) · n log N )
time and O(n log N + S(n, N )) space. Hence, using Theorem 6, we can ﬁnd
all palindromes in the string in O(n log log n log N log∗ N + n log2 N log∗ N ) =
O(n log2 N log∗ N ) time and O(n log∗ N + w) space.
⊓
⊔
35

B.6

Proof of Theorem 8

Proof. It is shown in [14] that we can compute the Lyndon factorization of the
string in O(P (n, N )+ E(n, N )·n log n) time using O(n2 + S(n, N )) space. Hence,
using Theorem 6, we can compute the Lyndon factorization of the string in
O(n log log n log N log∗ N + n log n log N log∗ N ) = O(n log n log N log∗ N ) time.
We remark that since m ≤ n due to [14], the output size m is omitted in the
total time complexity.
⊓
⊔
B.7

Proof of Theorem 9

Proof. In the preprocessing phase, we construct an H(log w′ , w′ ) for a signature
encoding G = (Σ, V, D, S) of size w′ such that
id (val (X1 )), . . . , id (val (Xn )) ∈ V using Lemma 24, spending O(n log log n log N log∗ M )
time, where w′ = O(n log N log∗ M ). Next we construct a compacted trie of size
O(m) that represents the m patterns, which we denote by PTree (pattern tree).
Formally, each non-root node of PTree represents either a pattern or the longest
common preﬁx of some pair of patterns. PTree can be built by using LCP of Theorem 5 in O(m log m log N ) time. We let each node have its string depth, and
the pointer to its deepest ancestor node that represents a pattern if such exists.
Further, we augment PTree with a data structure for level ancestor queries so
that we can locate any preﬁx of any pattern, designated by a pattern and length,
in PTree in O(log m) time by locating the string depth by binary search on the
path from the root to the node representing the pattern. Supposing that we know
the longest preﬁx of T [i..|T |] that is also a preﬁx of one of the patterns, which
we call the max-prefix for i, PTree allows us to output occ i patterns occurring at
position i in O(log m + occ i ) time. Hence, the pattern matching problem reduces
to computing the max-preﬁx for every position.
In the pattern matching phase, our algorithm processes T in a streaming
fashion, i.e., each character is processed in increasing order and discarded before taking the next character. Just before processing T [j + 1], the algorithm
maintains a pair of signature p and integer l such that val (p)[1..l] is the longest
suﬃx of T [1..j] that is also a preﬁx of one of the patterns. When T [j + 1] comes,
we search for the smallest position i ∈ {j − l + 1, . . . , j + 1} such that there
is a pattern whose preﬁx is T [i..j + 1]. For each i ∈ {j − l + 1, . . . , j + 1} in
increasing order, we check if there exists a pattern whose preﬁx is T [i..j + 1] by
binary search on a sorted list of m patterns. Since T [i..j] = val (p)[i − j + l..l],
LCE with p can be used for comparing a pattern preﬁx and T [i..j + 1] (except
for the last character T [j + 1]), and hence, the binary search is conducted in
O(log m log N log∗ M ) time. For each i, if there is no pattern whose preﬁx is
T [i..j + 1], we actually have computed the max-preﬁx for i, and then we output
the occurrences of patterns at i. The time complexity is dominated by the binary
search, which takes place O(|T |) times in total. Therefore, the algorithm runs in
O(|T | log m log N log∗ N + occ) time.
By the way, one might want to know occurrences of patterns as soon as
they appear as Aho-Corasick automata do it by reporting the occurrences of
36

the patterns by their ending positions. Our algorithm described above can be
modiﬁed to support it without changing the time and space complexities. In the
preprocessing phase, we additionally compute RPTree (reversed pattern tree),
which is analogue to PTree but deﬁned on the reversed strings of the patterns,
i.e., RPTree is the compacted trie of size O(m) that represents the reversed
strings of the m patterns. Let T [i..j] be the longest suﬃx of T [1..j] that is also
a preﬁx of one of the patterns. A suﬃx T [i′ ..j] of T [i..j] is called the max-suffix
for j iﬀ it is the longest suﬃx of T [i..j] that is also a suﬃx of one of the patterns.
Supposing that we know the max-suﬃx for j, RPTree allows us to output eocc j
patterns occurring with ending position j in O(log m + eocc j ) time. Given a pair
of signature p and integer l such that T [i..j] = val (p)[1..l], the max-suﬃx for j
can be computed in O(log m log N log∗ N ) time by binary search on a list of m
patterns sorted by their “reversed” strings since each comparison can be done
by “leftward” LCE with p. Except that we compute the max-suﬃx for every
position and output the patterns ending at each position, everything else is the
same as the previous algorithm, and hence, the time and space complexities are
not changed.

37

References used in Appendix
33. Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest
common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2), 75–94
(2005)
34. Rytter, W.: Application of Lempel-Ziv factorization to the approximation of
grammar-based compression. Theor. Comput. Sci. 302(1–3), 211–222 (2003)

38

