An In-place Framework for Exact and Approximate
Shortest Unique Substring Queries ⋆
Wing-Kai Hon1 , Sharma V. Thankachan2 , and Bojian Xu3 ⋆⋆
1

Department of CS, National Tsing Hua University, Taiwan
School of CSE, Georgia Institute of Technology, USA
3
Department of CS, Eastern Washington University, USA
wkhon@cs.nthu.edu.tw, sthankac@cc.gatech.edu, bojianxu@ewu.edu

arXiv:1512.00378v1 [] 1 Dec 2015

2

Abstract. We revisit the exact shortest unique substring (SUS) finding problem, and propose its approximate version where mismatches are allowed, due to its applications in subfields such as computational biology. We design
a generic in-place framework that fits to solve both the exact and approximate k-mismatch SUS finding, using the
minimum 2n memory words plus n bytes space, where n is the input string size. By using the in-place framework,
we can find the exact and approximate k-mismatch SUS for every string position using a total of O(n) and O(n2 )
time, respectively, regardless of the value of k. Our framework does not involve any compressed or succinct data
structures and thus is practical and easy to implement.

Keywords: string pattern matching, shortest unique substring, in-place algorithms

1 Introduction
We consider a string S[1..n], where each character S[i] is drawn from an alphabet Σ = {1, 2, . . . , σ}. We
say the character S[i] occupies the string position i. A substring S[i..j] of S represents S[i]S[i + 1] . . . S[j]
if 1 ≤ i ≤ j ≤ n, and is an empty string if i > j. We call i the start position and j the ending position of
S[i..j]. We say the substring S[i..j] covers the kth position of S, if i ≤ k ≤ j. String S[i′ ..j ′ ] is a proper
substring of another string S[i..j] if i ≤ i′ ≤ j ′ ≤ j and j ′ − i′ < j − i. The length of a non-empty
substring S[i..j], denoted as |S[i..j]|, is j − i + 1. We define the length of an empty string as zero.
The Hamming distance of two non-empty strings A and B of equal length, denoted as H(A, B), is
defined as the number of string positions where the characters differ. A substring S[i..j] is k-mismatch
unique, for some k ≥ 0, if there does not exist another substring S[i′ ..j ′ ], such that i′ 6= i, j − i = j ′ − i′ ,
and H(S[i..j], S[i′ ..j ′ ]) ≤ k. A substring is a k-mismatch repeat if it is not k-mismatch unique.
Definition 1 (k-mismatch SUS). For a particular string position p in S and an integer k, 0 ≤ k ≤ n − 1,
the k-mismatch shortest unique substring (SUS) covering position p, denoted as SUS kp , is a k-mismatch
unique substring S[i..j], such that (1) i ≤ p ≤ j, and (2) there does not exist another k-mismatch unique
substring S[i′ ..j ′ ], such that i′ ≤ p ≤ j ′ and j ′ − i′ < j − i.
We call 0-mismatch SUS as exact SUS, and the case k > 0 as approximate SUS.
For any k and p, SUS kp must exist, because at least the string S can be SUS kp , if none of its proper
substrings is SUS kp . On the other hand, there might be multiple choices for SUS kp . For example, if S =
abcbb, SUS 02 can be either S[1, 2] = ab or S[2, 3] = bc, and SUS 12 can be either S[1..3] = abc or
⋆

⋆⋆

Authors are listed in alphabetical order. A preliminary version of this paper appears in Proceedings of the 26th International
Symposium on Algorithms and Computation (ISAAC), Nagoya, Japan, 2015.
Corresponding author. Phone: +1 (509) 359-2817. Fax: +1 (509) 359-2215.

S[2..4] = bcb. Note that in Definition 1, we require k < n, because finding SUS np is trivial: SUS np ≡ S for
any string position p.
Problem (k-mismatch SUS finding). Given the string S, the value of k ≥ 0, and two empty integer arrays
A and B, we want to work in the place of S, A, and B, such that, in the end of computation: (1) S does
not
of the rightmost4 SUS ki , i.e.,
 change. (2) Each k(A[i], B[i]) pair saves the start and ending positions
2
S A[i]..B[i] = SUS i , using a total of O(n) time for k = 0 and O(n ) time for any k ≥ 1.
1.1

Prior work and our contribution

Exact SUS finding was proposed and studied recently by Pei et al. [7], due to its application in locating
snippets in document search, event analysis, and bioinformatics, such as finding the distinctness between
closely related organisms [3], polymerase chain reaction (PCR) primer design in molecular biology, genome
mapability [2], and next-generation short reads sequencing [1]. The algorithm in [7] can find all exact SUS
in O(n2 ) time using a suffix tree of O(n) space. Following their proposal, there has been a sequence of
improvements [8,5] for exact SUS finding, reducing the time cost from O(n2 ) to O(n) and alleviating the
underlying data structure from suffix tree to suffix array of O(n) space. Hu et al. [4] proposed an RMQ
(range minimum query) technique based indexing structure, which can be constructed in O(n) time and
space, such that any future exact SUS covering any interval of string positions can be answered in O(1)
time. In this work, we make the following contributions:
– We revisit the exact SUS finding problem and also propose its approximate version where mismatches
are allowed, which significantly increases the difficulty as well as the usage of SUS finding in subfields
such as bioinformatics, where approximate string matching is unavoidable due to genetic mutation and
errors in biological experiments.
– We propose a generic in-place algorithmic framework that fits to solve both the exact and approximate
k-mismatch SUS finding, using 2n words plus n bytes space. It is worth mentioning that 2n words plus
n bytes is the minimum memory space needed to save those n calculated SUSes: (1) It needs 2 words
to save each SUS by saving its start and ending positions (or one endpoint and its length) and there are
n SUSes. (2) It needs another n bytes to save the original string S in order to output the actual content
of any SUS of interest from queries. Note that all prior work [7,8,5,4] use O(n) space but there is big
leading constant hidden within the big-oh notation (see the experimental study in [5]).
– After the suffix array is constructed, all the computation in our solution happens in the place of two
integer arrays, using non-trivial techniques. It is worth noting that our solution does not involve any
compressed or succinct data structures, making our solution practical and easy to implement. Our preliminary experimental study shows that our solution for exact SUS finding is even faster than the fastest
one among [7,8,5]5 , in addition to a lot more space saving than them, enabling our solution to handle
larger data sets. Due to page limit, we will deliver the details of our experimental study in the journal
version of this paper.

2 Preparation
A prefix of S is a substring S[1..i], 1 ≤ i ≤ n. A proper prefix S[1..i] is a prefix of S where i < n. A
suffix of S is a substring S[i..n], denoted as Si , 1 ≤ i ≤ n. Si is a proper suffix of S, if i > 1.
4

5

Since any SUS may have multiple choices, it is our arbitrary decision to resolve the ties by picking the rightmost choice.
However, our solution can also be easily modified to find the leftmost choice.
Note that the work of [4] studies a different problem and its computation is of the query-answer model, and thus is not comparable
with [7,8,5] and ours.

2

For two strings A and B, we write A = B (and say A is equal to B), if |A| = |B| and H(A, B) = 0.
We say A is lexicographically smaller than B, denoted as A < B, if (1) A is a proper prefix of B, or (2)
A[1] < B[1], or (3) there exists an integer k > 1 such that A[i] = B[i] for all 1 ≤ i ≤ k−1 but A[k] < B[k].
The suffix array SA[1..n] of the string S is a permutation of {1, 2, . . . , n}, such that for any i and j,
1 ≤ i < j ≤ n, we have S[SA[i]..n] < S[SA[j]..n]. That is, SA[i] is the start position of the ith smallest
suffix in the lexicographic order. The rank array RA[1..n] is the inverse of the suffix array, i.e., RA[i] = j
iff SA[j] = i. The k-mismatch longest common prefix (LCP) between two strings A and B, k ≥ 0,
denoted as LCP k (A, B), is the LCP of A and B within Hamming distance k. For example, if A = abc and
B = acb, then: LCP 0 (A, B) is A[1] = B[1] = a and | LCP 0 (A, B)| = 1; LCP 1 (A, B) is A[1..2] = ab
and B[1, 2] = ac and | LCP 1 (A, B)| = 2.
Definition 2 (k-mismatch LSUS). For a particular string position p in S and an integer k, 0 ≤ k ≤ n − 1,
the k-mismatch left-bounded shortest unique substring (LSUS) starting at position p, denoted as LSUS kp ,
is a k-mismatch unique substring S[p..j], such that either p = j or any proper prefix of S[p..j] is not
k-mismatch unique.
We call 0-mismatch LSUS as exact LSUS, and the case k > 0 as approximate LSUS.
Observe that for any k, LSUS k1 = SUS k1 always exists, because at least the whole string S can be
LSUS k1 . However, for any k ≥ 0 and p ≥ 2, LSUS kp may not exist. For example, if S = dabcabc, none of
LSUS 0i and LSUS 1j exists, for all i ≥ 5, j ≥ 4. It follows that some string positions may not be covered by
any k-mismatch LSUS. For example, for the same string S = dabcabc, positions 6 and 7 are not covered
by any exact or 1-mismatch LSUS. On the other hand, if any LSUS kp does exist, there must be only one
choice for LSUS kp , because LSUS kp has its start position fixed on p and need to be as short as possible. Note
that in Definition 2, we require k < n, because finding LSUS np is trivial as LSUS n1 ≡ S and LSUS np does
not exist for all p > 1.
Definition 3 (k-mismatch SLS). For a particular string position p in S and an integer k, 0 ≤ k ≤ n − 1,
we use SLS kp to denote the shortest k-mismatch LSUS covering position p.
We call 0-mismatch SLS as exact SLS, and the case k > 0 as approximate SLS.
SLS kp may not exist, since position p may not be covered by any k-mismatch LSUS at all. For example,
if S = dabcabc, then none of SLS 0p and SLS 1p exists, for all p ≥ 6. On the other hand, if SLS kp exists, there
might be multiple choices for SLS kp . For example, if S = abcbac, SLS 02 can be either LSUS 01 = S[1..2]
or LSUS 02 = S[2..3], and SLS 13 can be any one of LSUS 11 = S[1..3], LSUS 12 = S[2..4], and LSUS 13 =
S[3..5]. Note that in Definition 3, we require k < n, because finding SLS np is trivial as SLS np ≡ S for all p.
Lemma 1. For any k and p: (1) LSUS k1 always exists. (2) If LSUS kp exists, then LSUS ki exists, for all
i ≤ p. (3) If LSUS kp does not exist, then none of LSUS ki exists, for all i ≥ p.
Proof. (1) LSUS k1 must exist, because at least the string S can be LSUS k1 if every proper prefix of S is a
k-mismatch repeat. (2) If LSUS kp exists, say LSUS kp = S[p..q], q ≥ p, then LSUS ki exists for every i ≤ p,
because at least S[i..q] is k-mismatch unique. (3) It is true, because otherwise we get a contradiction to the
second statement in the lemma.
⊔
⊓
Lemma 2. For any k and p, | LSUS kp | ≥ | LSUS kp−1 | − 1, if LSUS kp exists.
Proof. Suppose the k-mismatch substring LSUS kp = S[p..q], for some q ≥ p. Then, S[p − 1..q] is also
k-mismatch unique. It follows immediately that, | LSUS kp−1 | ≤ |S[p − 1..q]| = 1 + | LSUS kp |.
⊔
⊓
3

Lemma 3. For any k and p, SUS kp is either SLS kp or S[i..p], for some i, i + | LSUS ki | − 1 < p. That is,
SUS kp is either the shortest k-mismatch LSUS that covers position p, or a right extension (through position
p) of a k-mismatch LSUS.
Proof. We know SUS kp must exist, because at least the string S can be SUS kp . Let’s say SUS kp = S[i..j],
i ≤ p ≤ j. If S[i..j] is neither LSUS ki nor a right extension of LSUS ki , it means S[i..j] is a proper prefix
of LSUS ki and thus is a k-mismatch repeat, which is a contradiction to the fact that S[i..j] = SUS kp is
k-mismatch unique. Therefore, SUS kp = S[i..j] is either LSUS ki , or a right extension of LSUS ki (clearly,
j ≡ p in this case). Further, if SUS kp = S[i..j] = LSUS ki , it is obvious that LSUS ki must be the shortest
k-mismatch LSUS covering position p, i.e., SUS kp = SLS kp .
⊔
⊓
For example, let S = dabcabc, then: (1) SUS 03 can be either S[3..5] = LSUS 03 , or S[1..3], which is a
right extension of LSUS 01 = S[1]. (2) SUS 05 = S[4..5] = LSUS 04 . (3) SUS 06 = S[4..6], which is a right
extension of LSUS 04 = S[4..5]. (4) SUS 14 = S[3..5] = LSUS 13 . (5) SUS 16 = S[3..6], which is a right
extension of LSUS 13 .
The next lemma further says that if SUS kp is an extension of an k-mismatch LSUS, SUS kp can be quickly
obtained from SUS kp−1 .
Lemma 4. For any k and p, if SUS kp = S[i..p] and i + | LSUS ki | − 1 < p, i.e., SUS kp is a right extension
(through position p) of LSUS ki , then the following must be true: (1) p > 2; (2) the rightmost character of
SUS kp−1 is S[p − 1]; (3) SUS kp = SUS kp−1 S[p], the substring SUS kp−1 appended by the character S[p].
Proof. If SUS kp is a right extension (through position p) of a k-mismatch LSUS, it is certain that p > 1,
because SUS k1 ≡ LSUS k1 , which always exists (Lemma 1).
Because SUS kp is a right extension (through position p) of a k-mismatch LSUS, we have SUS kp =
S[i..p] for some i < p, and LSUS ki = S[i..j] for some j < p. We also know S[i..p − 1] is k-mismatch
unique, because the k-mismatch unique substring S[i..j] is a prefix of S[i..p − 1]. Note that any substring
starting from a position before i and covering position p − 1 is longer than the k-mismatch unique substring
S[i..p − 1], so SUS kp−1 must be starting from a position between i and p − 1, inclusive. Next, we show
SUS kp−1 actually must start at position i.
The fact that SUS kp = S[i..p] implies | LSUS kt | ≥ | SUS kp | = p − i + 1 for every t = i + 1, i + 2, . . . , p;
otherwise, rather than S[i..p], any one of these LSUS kt whose size is smaller than p − i + 1 would be a better
choice for SUS kp . That means, any k-mismatch unique substring starting from t = i + 1, i + 2, . . . , p − 1
has a length at least p − i + 1. However, |S[i..p − 1]| = p − i < p − i + 1 and S[i..p − 1] is k-mismatch
unique already and covers position p − 1 as well, so S[i..p − 1] is the only choice for SUS kp−1 . This also
means SUS kp is indeed the substring SUS kp−1 appended by the character S[p].
⊔
⊓

3 The High-Level Picture
In this section, we present an overview of our in-place framework for finding both the exact and approximate
SUS. The framework is composed of three stages, where all computation happens in the place of three arrays,
S, A, and B, each of size n. Arrays A and B are of integers, whereas array S always saves the input string.
The following table summarizes the roles of A and B at different stages by showing their content at the end
of each stage.
4

Stages
1
2
3

A[i]

B[i]

Used as temporary workspace during stage 1, but Ending position of LSUS ki , if LSUS ki exthe content is useless for stages 2 and 3.
ists; otherwise, NIL.
The largest j, such that LSUS kj is an SLS ki , if Ending position of LSUS ki , if LSUS ki exists; otherwise, NIL.
SLS ki exists; otherwise, NIL.
Start position of the rightmost SUS ki
Ending position of the rightmost SUS ki

Stage 1 (Section 4). We take the array S that saves the input string as input to compute LSUS ki for all
i, in the place of A and B. At the end of the stage, each B[i] saves the ending position of LSUS ki , if
LSUS ki exists. Since each existing LSUS ki has its start position fixed at i, at the end of stage 1, each existing
LSUS ki = S i..B[i] . For those non-existing k-mismatch LSUSes, we assign NIL to the corresponding
B array elements. The time cost of this stage is O(n) for exact LSUS finding (k = 0), and is O(n2 ) for
approximate LSUS finding, for any k ≥ 1.
Stage 2 (Section 5). Given the array B (i.e., the k-mismatch LSUS array of S) from stage 1, we compute
the rightmost SLS ki , the rightmost shortest LSUS covering position i, for all i, in the place of A and B. At
the end of stage 2, each A[i] saves the largest j, such that LSUS kj is an SLS ki , i.e., the rightmost SLS ki =


S A[i]..B[A[i]] , if SLS ki exists; otherwise, we assign A[i] = NIL. Array B does not change during stage 2.
The time cost of this stage is O(n), for any k ≥ 0.
Stage 3 (Section 6). Given A and B from stage 2, we compute SUS ki , for all i, in the place of A and B.
At the end of
stage 3, each (A[i], B[i]) pair saves the start and ending positions of the rightmost SUS ki , i.e.,

SUS ki = S A[i]..B[i] . The time cost of this stage is O(n), for any k ≥ 0.
Algorithms 1, 2, 3, and 4 in the appendix give the pseudocode of the in-place procedures that we will
describe in Sections 4.1, 4.2, 5, and 6, respectively.

4 Finding k-mismatch LSUS
The goal of this section is that, given the input string S and two integer arrays A and B, we want to work in
the place of A and B, such that B[i] saves the ending position of LSUS ki for all existing LSUS ki ; otherwise,
B[i] is assigned NIL. We take different approaches in finding the exact LSUS (k = 0) and approximate
LSUS (k ≥ 1).
4.1

Finding exact LSUS (k = 0)

Lemma 5 (Lemma 7.1 in [6]). Given the string S of size n, drawn from an alphabet of size σ, we can
construct the suffix array SA of S in O(n) time, using n + σ words plus n bytes, where the space of n bytes
saves S, the space of n words saves SA, and the extra space of σ words is used as the workspace for the run
of the SA construction algorithm.
Given the input string S, we first use the O(n)-time suffix array construction algorithm from [6] to create
the SA of S, where the array A is used to save the SA and the array B is used as the workspace. Note that
σ ≤ n is always true, because otherwise we will prune from the alphabet those characters that do not appear
in the string. After SA (saved in A) is constructed, we can easily spend another O(n) time to create the rank
array RA of S (saved in B): RA[SA[i]] ← i (i.e., B[A[i]] ← i), for all i. Next, we use and work in the place
of A (i.e., SA) and B (i.e., RA) to compute the ending position of each existing LSUS 0i and save the result
in B[i], using another O(n) time.
5

Definition 4.


LCP 0 S[i..n], S [SA [RA[i] − 1] ..n] , if RA[i] > 1
xi =
0,
otherwise


LCP 0 S[i..n], S [SA [RA[i] + 1] ..n] , if RA[i] < n
yi =
0,
otherwise


That is, xi (yi , resp.) is the length of the longest common prefix of S[i..n] and its lexicographically preceding
(succeeding, resp.) suffix, if the preceding (succeeding, resp.) suffix exists.
Fact 1 For every string position i, 1 ≤ i ≤ n:

S [i..i + max{xi , yi }] , if i + max{xi , yi } ≤ n
0
LSUS i =
not existing,
otherwise.
First, observe that in the sequence of xi ’s, if xi > 0, then xi+1 ≥ xi − 1 must be true, because at least
S[SA[RA[i] − 1] + 1..n] can be the lexicographically preceding suffix of S[i + 1..n], and they share the
leading xi − 1 characters. That means, when we compute xi+1 , we can skip over the comparisons of the
first xi − 1 pair of characters between S[i + 1..n] and its lexicographically preceding suffix. It follows that,
given the SA and RA of S and using the above observation, we can compute the sequence of xi ’s in O(n)
time. Using the similar observation, we can compute the sequence of yi ’s in O(n) time, provided that S and
its SA and RA are given.
Second, since we can compute the sequences of xi ’s and yi ’s in parallel (i.e., compute the sequence of
(xi , yi ) pairs), we can use Fact 1 to compute the sequence of LSUS 0i in O(n) time. Further, since RA[i] is
used only for retrieving the lexicographically preceding and succeeding suffixes of S[i..n] when we compute
the pair (xi , yi ), we can save each computed LSUS 0i (indeed, i+max{xi , yi }, the ending position of LSUS 0i )
in the place of RA[i] (i.e., B[i]). In the case i + max{xi , yi } > n, meaning LSUS 0i does not exist,we will
assign NIL to RA[j] (i.e., B[j]) for all j ≥ i (Lemma 1). The overall time cost for computing the sequence
of LSUS 0i is thus O(n), yielding the following lemma.
Lemma 6. Given the character array S of size n that saves the input string, and the integer arrays A and
B, each of size n, we can work in the place of S, A, and B, using O(n) time, such that at the end of the
computation, S does not change, B[i] saves the ending of position of LSUS 0i , if LSUS 0i exists (otherwise,
B[i] = NIL).
4.2

Finding approximate LSUS (k ≥ 1)

Definition 5. For a particular string position p in S and an integer k, 0 ≤ k ≤ n − 1, the k-mismatch
left-bounded longest repeat (LLR) starting at position p, denoted as LLR kp , is a k-mismatch repeat S[p..j],
such that either j = n or S[p..j + 1] is k-mismatch unique.
Fact 2 (1) If | LLR kp | < n − p + 1, i.e., the ending position of LLR kp is less than n, then LSUS kp =


S p..p + | LLR kp | , the substring of LLR kp appended by the character following LLR kp . (2) Otherwise,
LSUS kp does not exist.
Our high-level strategy for finding LSUS ki for all i is as follows. We first find LLR ki for all i. Then we
use Fact 2 to find each LSUS ki from LLR ki : If LLR ki does not end on position n, we will extend it for one
more character on its right side and make the extension to be LSUS ki ; otherwise, LLR ki does not exist. Next,
we explain how to find LLR ki , for all i.
6

Clearly, | LLR ki | = max{| LCP k (Si , Sj )|, j 6= i}, for all i. The way we calculate | LLR ki | for all i is
simply to let every pair of two distinct suffixes to be compared with each other. In order to do so, we work
over n − 1 phases, named as P1 through Pn−1 . On a particular phase Pδ , we compare suffixes Si and Si−δ
for all i = n, n − 1, . . . , δ + 1. Obviously, over these n − 1 phases, every pair of distinct suffixes have
been compared with each other exactly once. Over these n − 1 phases, we simply record in B[i], which is
initialized to be 0, the length of the longest k-mismatch LCP that each suffix Si has seen when compared
with any other suffixes. Next, we explain the details of a particular phase Pδ .
On a particular phase Pδ , 1 ≤ δ ≤ n−1, we compare suffixes Si and Si−δ for all i = n, n−1, . . . , δ +1.
When we compare Si and Si−δ , we save in A[1..k + 1], which is initialized to be empty at the beginning
of each phase, the leftmost mismatched k + 1 positions in Si . We will see later how to update A[1..k + 1]
efficiently over the progress of a particular phase and use it to update the B array.
We treat A[1..k + 1] as a circular array, i.e., i − 1 = k + 1 when i = 1, and i + 1 = 1 when i = k + 1. Let
size, which is initialized to be 0 at the beginning of each phase, denote the number of mismatched positions
being saved in A[1..k + 1] so far in Pδ . We can describe the work of phase Pδ , inductively, as follows.
1. We compare Sn and Sn−δ by only comparing S[n] and S[n − δ], since Sn = S[n].
(a) If S[n] 6= S[n − δ]: Save n in any position in A[1..k + 1]; size ← 1.
(b) B[n] ← max{B[n], 1}; B[n − δ] ← max{B[n − δ], 1}.
2. Suppose we have finished the comparison between the suffixes Si+1 and Si+1−δ , for some i, δ + 1 ≤
i ≤ n − 1. The leftmost k + 1 mismatched positions (if existing) between them have been saved in the
circular array A[1..k + 1]. Let A[cursor] be the element that is saving the first mismatched position (if
existing) between the two suffixes.
3. Next, we compare the suffixes Si and Si−δ by only comparing S[i] and S[i − δ], since Si+1 and Si+1−δ
have been compared. Remind that cursor − 1 below is in its cyclic manner.
(a) If S[i] 6= S[i − δ]: cursor ← cursor − 1; Save i in A[cursor] and overwrite the old content in
A[cursor] if there is; size ← min{size + 1, k + 1}.
(b) If size < k + 1: B[i] ← max{B[i], n − i + 1}; B[i − δ] ← max{B[i − δ], n − i + 1}.
(c) Else: B[i] ← max{B[i], A[cursor − 1] − i}; B[i − δ] ← max{B[i − δ], A[cursor − 1] − i}. Note
that A[cursor − 1] is saving the (k + 1)th mismatched position between Si and Si−δ .
After the computation of all LLR ki is finished, using the above n−1 phases, each B[i] is saving | LLR ki |.
Next, we can use Fact 2 to convert each LLR ki to LSUS ki by simply checking each B[i]: If i + B[i] − 1 < n,
i.e., LLR ki does not end on position n, then we assigne B[i] = i + B[i], the ending position of LSUS ki ;
otherwise, we assign B[i] = NIL, meaning LSUS ki does not exist.
The computation of all LLR ki takes n−1 phases and each phase clearly has no more than n comparisons,
giving a total of O(n2 ) time cost. The procedure of converting each LLR ki to LSUS ki spends another O(n)
time. Altogether, we get an O(n2 )-time in-place procedure for finding approximate LSUS, for any k ≥ 1.
Lemma 7. Given the character array S of size n that saves the input string, the integer arrays A and B,
each of size n, and the value of integer k ≥ 1, we can work in the place of S, A, and B, using O(n2 ) time,
such that at the end of the computation, S does not change, B[i] saves the ending of position of LSUS ki , i.e.,
LSUS ki = S[i..B[i]], if LSUS ki exists; otherwise, B[i] = NIL.
7

5 Finding k-mismatch SLS
Now we are given the array B, where each B[i] saves the ending position of LSUS ki if LSUS ki exists
and NIL otherwise. In this section, we want to work in the place of A and B, such that in the end of
computation: A[i] saves j, such that LSUS kj is the rightmost SLS ki , if such j exists; otherwise, A[i] = NIL.


That means, in the end of this section, the rightmost SLS ki = S A[i]..B[A[i]] , if SLS ki exists; otherwise,
A[i] = B[i] = NIL.
Recall that some k-mismatch LSUS may not exist and some positions may not be covered by any kmismatch LSUS (see the examples after Definition 2). Further, due to Lemmas 1 and 2, we know such
positions that are not covered by any k-mismatch LSUS must comprise a continuous chunk on the right end
of string S.
Definition 6. Let LSUS kr , 1 ≤ r ≤ n, be the rightmost existing k-mismatch LSUS of the input string S. Let
z, 1 ≤ z ≤ n, be the rightmost string position that is covered by any k-mismatch LSUS of the string S.
Again, due to Lemmas 1 and 2, it is trivial to find the values of r and z in O(n) time: scan array B (i.e.
LSUS array) from right to left, and stop when seeing the first non-NIL B array element, which is exactly
B[r], then z = B[r]. If z < n, we can then simply set A[i] = NIL for all i > z. Recall that B[i] = NIL
already for all i > r from stage 1. In the rest of this section, we only need to work with the two subarrays
A[1..z] and B[1..z], wanting to make A[i] to be the start position of the rightmost SLS ki , for all i ≤ z.
Let B[1..z] and an integer r, 1 ≤ r ≤ z, be the input, where (1) B[1..r] is of monotonically nondecreasing integers (Lemma 2), with i ≤ B[i], (2) B[r + 1..z] are all NIL, if r < z, and (3) B[r] = z.
We can use each B[i], i ≤ r, as a compact representation of the interval Ii = (i, B[i]). Let I = { Ii |
i ∈ [1..r] }, and ℓi = |B[i] − i + 1| be the length of Ii . Let A[1..z] be an output array such that A[j] = i,
where Ii is the rightmost shortest interval in I that covers j.
To illustrate the ideas and concepts that we will present in the rest of this section, let us use the following
as a running example, where r = 9, z = 15, and n = 17 (we add (0, B[0]) = (0, 0) as a sentinel).
i
B[i]
ℓi

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0 3 4 7 8 10 10 10 11 15 − − − − − − − −
0 3 3 5 5 6 5 4 4 7 − − − − − − − −

pred[i] − − − 2 2 4 2 2 2 8 − − − − − − − −
ti
− 1 2 5 5 9 6 7 8 12 − − − − − − − −
max t−1
− 1 2 −− 4 6 7 8 5 − − 9 − − − − −
i
A[i]

− 1 2 2 2 4 6 7 8 8 8 8 9 9 9 9 − −

Definition 7. For an interval
 Ii , wedefine the effective covering region with respect to the previous intervals
I<i = { Ik | k < i } to be ti , B[i] where
n
o
ti = max i, max {B[k] + 1 | Ik is shorter than Ii , k < i } .
We call ti the starting point of the effective covering region of Ii .
The effective covering region of Ii is exactly those regions that would set Ii as the answer, provided that all
the intervals I<i before Ii are present, and all the intervals I>i = { Ik | k > i } are absent.
−1
6
We next define t−1
i as a list , such that j ∈ ti if and only if tj = i. Observe that since ti ≥ i by definition,
any value j in t−1
i must have j ≤ i, and the effective region of Ij must cover i.
6

In actual run, t−1
saves the largest number in that list, as we will see more clearly later.
i

8

Lemma 8. For i = 1, 2, . . . , z:
A[i] = max

i
[

−1
t−1
k = max { A[i − 1], max ti }.

k=1

Si

Proof. Let j = max k=1 t−1
k . This means that for the effective region of any Ih , with h > j, none of
them covers i. Next, observe that Ij must cover i; otherwise, for all the intervals Ih with h < j, we have
B[h] ≤ B[j] < i, so that none of them can cover i, and thus a contradiction occurs. Finally, we show that
for those h < j, Ih can be pruned by Ij , thus implying that A[i] = j is a correct answer.
Consider all those h with h < j:
1. If Ih is longer than Ij , Ih can be pruned away directly.
2. Else, if Ih and Ij have equal length, Ih can be pruned away also, regardless of its coverage on i, since
we pick the rightmost shortest
interval that covers i.
Si
−1
3. Else, h must appear in k=1 tk . By the definition of tj , we have B[h] < tj ≤ i; thus, Ih does not cover
i, and can be pruned away.
Thus, the first equality in the lemma follows, while the second equality in the lemma is trivial once we have
the first equality.
⊔
⊓
Lemma 9. Suppose that all ti , 1 ≤ i ≤ r, can be generated incrementally in O(n) time. Then, we can
obtain all max t−1
i , 1 ≤ i ≤ z, in O(n) time.
Proof. We examine each ti , i = 1, 2, . . . , r, and write i at entry ti = j of the t−1 array; if such an entry
contains a value i′ already, we simply overwrite i′ with the latter i.
⊔
⊓
Indeed, we may scan ti from right to left, i.e., i = r, r − 1, . . . , 1, and update max t−1
as we proceed.
i
Firstly, if ti > i, we set t−1
=
undefined.
Else,
let
j
=
t
(whose
value
is
at
least
i),
and
we
check if t−1
i
i
j is
−1
defined: If not, simply set tj = i; otherwise, no update is needed.
The advantage of the ‘right-to-left’ approach is that we can construct t−1
i in-place, by re-using the memory
space of ti . To see why it is so, by the time we need to update a certain entry j = ti at step i, the information
tj has been used (and will never be used), so that we can safely overwrite the original entry, storing tj , to
store t−1
j instead. This gives the following corollary.
Corollary 1. Suppose that all ti ’s are generated, and are stored in a certain array A[1..z]. Then, we can
obtain max ti−1 for all i’s, in-place, by storing the results in the same array A[1..z]; the time cost is O(n).
Our goal is to make our algorithm in-place. Suppose that we can have in-place incremental generation of ti .
Then, by the above lemma, we may store max t−1
i temporarily at A[i]; afterwards, by the second equality
of Lemma 8, we can compute the correct output A by a simple scan of A from left to right.
Thus, to make the whole process in-place, it remains to show how ti can be computed in O(n) time, inplace. For this, we define pred[i] to be the largest j (if it exists) such that j < i and length of Ij is shorter than
Ii . It is easy to check that if pred[i] = j is defined, then ti = max { B[j] + 1, i } (and ti = i otherwise).7
Moreover, pred[i] for all i’s can be computed incrementally, with a way analogous to the construction of
the failure function in KMP algorithm: we check pred[i − 1], pred[pred[i − 1]], pred[pred[pred[i − 1]],
7

For each j ′ < j, if Ij ′ covers i, Ij would also cover i; in such a case, B[j] + 1 ≥ B[j ′ ] + 1. For each j ′ ∈ [pred[i], i − 1], Ij ′
is longer than Ii .

9

and so on, until we obtain j in the process such that Ij is shorter than Ii , and set pred[i] := j.8 If such j
does not exist, we set pred[i] = NIL. The running time is bounded by O(n).
This gives the following O(n)-time in-place algorithm (where B is read-only):
1. Compute pred[i], i = 1, 2, . . . , r, and store this in A[i]. Note that this step requires the length information of the intervals of Ii , which can be obtained in O(1) time, on the fly, from B[i] .
2. Scan A[1..r] (i.e., pred) incrementally, and obtain ti from the above discussion. The value of ti is stored
in A[i]. Note that this step requires the access to the original B.
3. Scan A[1..r] (i.e., ti ) from right to left, and obtain max t−1
i decrementally (stored in A[i]) by Corollary 1.
4. Scan A[1..z] (i.e., max t−1
i ) incrementally (i = 1, 2, . . . , z), and obtain the desired A[i] by the second
equality in Lemma 8.
Lemma 10. Given the integer array A and B, each of size n, where each B[i] saves the ending position
of LSUS ki , if LSUS ki exists and NIL otherwise, we can work in the place of array A and B, using O(n)
time, such that, in the end of computation, array B does not change, and A[i] saves j, where LSUS kj is the


rightmost SLS ki , if such j exists; otherwise, A[i] = NIL. That is, SLS ki = S A[i]..B[A[i]] , if SLS ki exists;
otherwise, A[i] = B[i] = NIL.

6 Finding k-mismatch SUS
Now we have array A, where A[i] = j, such that LSUS kj is the rightmost SLS ki , if position i is covered
by any k-mismatch LSUS; otherwise, A[i] = NIL. Note that A[i] = j is recording the start position of
the rightmost SLS ki already, because LSUS kj starts on position j. We also have array B, where B[i] =
i + | LSUS ki | − 1, the ending position of LSUS ki , if LSUS ki exists; otherwise, B[i] = NIL.
Step I. We want to transform A and B, such that each (A[i], B[i]) pair saves the start and ending positions of
SLS ki , if SLS ki exists; otherwise, we set (A[i], B[i]) = (NIL, NIL). Since each A[i] is already recording the
start position of SLS ki already, as we have explained at the beginning of this section, we only need to make
changes to array B. We first set B[i] = NIL for all i > z (Definition 6). Then, we scan array B from right
to left, starting from position z through 1, and set each B[i] = B[A[i]], the ending position of the rightmost
SLS ki . Because the leftmost position that any existing LSUS ki can cover is position i, we know A[i] ≤ i
and we no longer need B[i] (i.e., the information of LSUS ki ) after SLS i is computed. Therefore, it is safe to
record SLS ki by overwriting B[i] by B[A[i]] (i.e., the ending position of SLS ki ), in this right-to-left scan.
Step II. We use arrays A and B to calculate SUS ki for each i and save the result in the place of A and B,
i.e., each (A[i], B[i]) pair saves the start and ending position of SUS ki . Because of Lemma 3 and 4, we can
use arrays A and B to compute each SUS ki inductively, as follows:


1. SUS k1 = LSUS k1 = SLS k1 = S A[1]..B[1] .
2. For i = 2, 3, . . . , n, we compute SUS ki :
k
k
be SUS ki−1 appended by
(a) If (A[i], B[i]) = (NIL, NIL), meaning
 SLS i does not exist,
 we set SUS i to
k
k
the character S[i], i.e., SUS i = S A[i − 1]..B[i − 1] + 1 , and save SUS i by setting (A[i], B[i]) =
(A[i − 1], B[i − 1] + 1);
8

Intuitively, pred defines the shortcuts so that we can skip some intervals in I<i to compute ti .

10



(b) Else, if SUS ki−1 ends at position i − 1 and SUS ki−1 S[i] = S A[i − 1]..B[i − 1] + 1 is shorter than


SLS ki = S A[i]..B[i] , we set (A[i], B[i]) = (A[i − 1], B[i − 1] + 1);
(c) Else, SUS ki = SLS ki and thus we leave A[i] and B[i] unchanged.
Lemma 11. Given arrays A and B:
– A[i] = j, such that LSUS kj is the rightmost SLS ki , if SLS ki exists; otherwise, A[i] = NIL;
– B[i] = i + | LSUS ki | − 1, the ending position of LSUS ki , if LSUS ki exists; otherwise, B[i] = NIL.
we can work in the place of A and B, using O(n) time, such that,
 in the end
 of computation, each (A[i], B[i])
saves the start and ending positions of SUS ki , i.e., SUS ki = S A[i]..B[i] , i = 1, 2, . . . , n.

By concatenating the claims in Lemmas 6, 7, 10, and 11, we get the final result.

Theorem 1. Given the array S of size n that saves the input string, two empty integer arrays A and B,
each of size n, and the value of integer k ≥ 0, we can work in the place of arrays S, A, and B, using a
total of O(n) time for k = 0 and O(n2 ) time for any k ≥ 1, such that in the end of computation, S does
k
not change, each (A[i],
 B[i]) pair represents the start and ending positions of the rightmost SUS i , i.e.,
k
SUS i = S A[i]..B[i] .

7 Conclusion
In this paper, we revisited the exact SUS finding problem, and proposed its approximate version where
mismatches are allowed, and thus significantly extended the usage of SUS finding in subfields such as
computational biology. We designed a generic in-place algorithmic framework that uses the minimum 2n
words plus n bytes space and can fit to find both exact and approximate k-mismatch SUS, with O(n) and
O(n2 ) time complexities, respectively, regardless of the value of any k ≥ 1. An urgent future work will
be researching for a faster (and still practical) in-place algorithm for finding approximate LSUS to replace
the current algorithm discussed in Section 4.2. Such new algorithm will lead to an overall faster in-place
solution for approximate SUS finding.

References
1. Adaş, B., Bayraktar, E., Faro, S., Moustafa, I., Külekci, M.O.: Nucleotide sequence alignment and compression via shortest
unique substring. In: Proceedings of the 3rd International Work-Conference on Bioinformatics and Biomedical Engineering
(IWBBIO). pp. 363–374 (2015)
2. Derrien, T., Estell, J., Marco Sola, S., Knowles, D.G., Raineri, E., Guig, R., Ribeca, P.: Fast computation and applications of
genome mappability. PLoS ONE 7(1), e30377 (01 2012)
3. Haubold, B., Pierstorff, N., Möller, F., Wiehe, T.: Genome comparison without alignment using shortest unique substrings. BMC
Bioinformatics 6, 123 (2005)
4. Hu, X., Pei, J., Tao, Y.: Shortest unique queries on strings. In: Proceedings of the 21st International Symposium on String
Processing and Information Retrieval (SPIRE). pp. 161–172 (2014)
5. İleri, A.M., Külekci, M.O., Xu, B.: A simple yet time-optimal and linear-space algorithm for shortest unique substring queries.
Theoretical Computer Science 562(0), 621 – 633 (2015), (also in CPM2014.)
6. Nong, G.: Practical linear-time O(1)-workspace suffix sorting for constant alphabets. ACM Transactions on Information Systems (TOIS) 31(3), 15:1–15:15 (Aug 2013)
7. Pei, J., Wu, W.C.H., Yeh, M.Y.: On shortest unique substring queries. In: Proceedings of IEEE International Conference on Data
Engineering (ICDE). pp. 937–948 (2013)
8. Tsuruta, K., Inenaga, S., Bannai, H., Takeda, M.: Shortest unique substrings queries in optimal time. In: Proceedings of International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). pp. 503–513 (2014)

11

Appendix

Algorithm 1: Finding exact LSUS
Input: String S and integer arrays A and B, each of size n.
Output: S does not change. B[i] = ending position of LSUS 0i , if LSUS 0i exists; otherwise, B[i] = NIL.
1

2

Create the SA of S using the suffix array construction algorithm from [6], where array A is used to save the resulting SA
and B is used as the workspace for the run of the algorithm.
/* Create the RA of S and save the result in the array B.
*/
for i = 1 . . . n do RA[SA[i]] ← i ;
// i.e., SA = A, RA = B, and B[A[i]] ← i.
/* From here on, A and SA are the same physical array. B, RA, and LSUS are the
same physical array.
*/

3
4
5
6

7
8
9
10

11
12
13
14
15
16
17
18

x ← 0; y ← 0;
for i = 1, 2, . . . , n do
if RA[i] > 1 then
j ← SA[RA[i] − 1];
/* Calculate the length of the 0-mismatch LCP between S [i..n] and its
lexicographically preceding suffix.
while S [i + x] = S [j + x] do x ← x + 1
else x ← 0;
if RA[i] < n then
j ← SA[RA[i] + 1];
/* Calculate the length of the 0-mismatch LCP between S [i..n] and its
lexicographically succeeding suffix.
while S [i + y] = S [j + y] do y ← y + 1;
else y ← 0;
if i + max{x, y} ≤ n then LSUS [i] ← i + max{x, y};
else
for j = i . . . n do LSUS [j] ← NIL;
Break;
if x > 0 then x ← x − 1;
if y > 0 then y ← y − 1;

12

*/

*/

// ending position of | LSUS i |
// LSUS i does not exist. Early stop.

Algorithm 2: Finding approximate LSUS
Input: String S and integer arrays A and B, each of size n, the value of k ≥ 1.
Output: S does not change. B[i] = ending position of LSUS ki , if LSUS 0i exists; otherwise, B[i] = NIL.
1

for i = 1 . . . n do B[i] ← 0 ;

// Initialization

/* We use A[1 . . . k + 1] as a circular array to save the k + 1 most recently found
mismatched positions.

*/

2

capacity ← k + 1;
// The capacity of the circular array that records at most k + 1
mismatched positions.

3

cursor ← 1;
// The index of the circular array position that is saving the most
recently founded mismatched position. It can be initialized to be any value from
{1, 2, . . . , capacity}.

4

for δ = 1 . . . n − 1 do
// n − 1 phases
size ← 0 ; // The number of recorded mismatched positions in the circular array in
the current phase.

5

6

for i = n down to δ + 1 do
/* Comparing suffixes Si and Si−δ by comparing their leading characters, as
their remaining characters have been compared in previous steps of this
phase.
*/

7
8
9
10

if S[i] 6= S[i − δ] then

cursor ← (cursor − 2 + capacity) mod capacity + 1;
A[cursor] ← i;
size ← min(size + 1, capacity);

13

if size < capacity then
B[i] ← max(B[i], n − i + 1) ;
B[i − δ] ← max(B[i − δ], n − i + 1);

14

else

11
12

15

// We use 1-based indexing.

// = size − i + 1






B[i] ← max B[i], A (cursor − 1 + k) mod capacity + 1 − i ;

// We use 1-based

indexing.
16

17
18
19






B[i − δ] ← max B[i − δ], A (cursor − 1 + k) mod capacity + 1 − i ;
for i = 1 . . . n do
if B[i] = size − i + 1 then B[i] ← NIL;
else B[i] ← i + B[i];

// LSUS ki does not exist.
// The ending position of LSUS ki .

13

Algorithm 3: Finding SLS (exact or approximate)
Input: Integer arrays A and B, each of size n. Each B[i] saves the ending position of LSUS ki , if LSUS ki exists; NIL,
otherwise.
Output: Array B does not change. Each A[i] = j, such that LSUS kj is the rightmost SLS ki , if SLS ki exists; otherwise,
A[i] = NIL.

1

/* Find the index of the rightmost existing k-mismatch LSUS.
for r = n down to 1 do if B[r] 6= NIL then break;

*/

/* Compute the pred array, using the memory space of A array. pred[i] is the largest
j, such that j < i and | LSUS kj | < |LSU Sik |, if such j exists; otherwise pred[i] = NIL.
If LSUS ki does not exist, pred[i] = NIL also. From here on, pred and A are the same
physical array.
*/
2

if r < n then for i = r + 1 . . . n do pred[i] ← NIL ; // Positions that do not have k-mismatch LSUS

3

pred[1] ← NIL;
for i = 2 . . . r do
ℓi ← B[i] − i + 1 ;
j ← i − 1;
while pred[j] 6= NIL and B[j] − j + 1 >= ℓi do j ← pred[j];
if B[j] − j + 1 < ℓi then pred[i] ← j; else pred[i] ← NIL;

4
5
6
7
8

// | LSUS ki |

/* Compute the t array, using the memory space of A array. t[i] is the start
position of the effective region of LSUS ki , if LSUS ki exists; NIL, otherwise.
From here on, t and A are the same physical array.
*/
9
10

for i = 1 . . . r do
if pred[i] = NIL then t[i] ← i; else t[i] ← max(B[pred[i]] + 1, i);
/* Compute the t−1 array, using the memory space of array A. t−1 [i] is the largest
j, such that the effective region of LSUS kj starts on position i, if such j
exists; otherwise, NIL. From here on, t−1 and A are the same physical array. */

11
12
13

for i = r down to 1 do
if t−1 [t[i]] = NIL then t−1 [t[i]] ← i;
if i < t[i] then t−1 [i] ← NIL;
// Enable us to update this place in the future when
needed.
/* Compute SLS array using the memory space of array A. SLS [i] = j, such that LSUS kj
is the rightmost SLS ki , if SLS ki exists; NIL, otherwise. From here on, SLS and A
are the same physical array.
*/

14
15

SLS [1] ← 1;
for i = 2 . . . B[r] do SLS [i] ← max(SLS [i − 1], t−1 [i]);

14

Algorithm 4: Finding SUS (exact or approximate)
Input: Integer arrays A and B, each of size n. (1) A[i] = j, such that LSUS kj is the rightmost SLS ki , if SLS ki exists;
otherwise, A[i] = NIL. (2) B[i] is the ending position of LSUS ki , if LSUS ki exists; otherwise, B[i] = NIL.
Output: Each (A[i], B[i]) pair represents the start and ending positions of SUS ki .
1
2
3

4
5
6
7
8
9

for i = n down to 1 do
if B[i] 6= NIL then
z ← i + B[i] − 1;
LSUS.
break;

// The rightmost position covered by at least one k-mismatch

if z < n then
for i = z + 1 . . . n do
B[i] ← NIL ;

// Positions not covered by any k-mismatch LSUS.

for i = z down to 1 do
B[i] ← B[A[i]] ;

// The ending position of SLS ki .



/* By this point, S A[i]..B[i] = SLS ki , if SLS ki exists; otherwise A[i] = B[i] = NIL.


Note that SUS k1 = SLS k1 = S A[1]..B[1] , which must be existing and has been
computed.
Next, we compute SUS ki for all i ≥ 2.
10
11
12
13
14

for i = 2 . . . n do
if A[i] = B[i] = NIL then
A[i] ← A[i − 1]; B[i] ← B[i − 1] + 1 ;

*/

// SUS ki = SUS ki−1 S[i]

else if B[i − 1] = i − 1 and B[i − 1] − A[i − 1] + 2 < B[i] − A[i] + 1 then
A[i] ← A[i − 1]; B[i] ← B[i − 1] + 1 ;
/* Otherwise, do nothing. SUS ki = SLS ki .

15

// SUS ki = SUS ki−1 S[i]
*/

