Lightweight Parameterized Suﬃx Array
Construction
Tomohiro I1 , Satoshi Deguchi1 , Hideo Bannai1 , Shunsuke Inenaga2 , andMasayuki Takeda1
1

2

Department of Informatics, Kyushu University
Faculty of Information Science and Electrical Engineering, Kyushu University
744 Motooka, Nishiku, Fukuoka, 819–0395 Japan.
{tomohiro.i,satoshi.deguchi,bannai,takeda}@i.kyushu-u.ac.jp
inenaga@c.csce.kyushu-u.ac.jp
Abstract. We present a ﬁrst algorithm for direct construction of parameterized suﬃx arrays and parameterized longest common preﬁx arraysfor non-binary strings. Experimental results show that our algorithm ismuch faster than naı̈ve methods.

1

Introduction

Parameterized pattern matching is a form of pattern matching ﬁrst introduced by
Baker [1], that allows for interchange in the alphabet. More formally, let Π be theset of parameter symbols and Σ be the set of constant symbols. Strings over Π ∪Σare called parameterized strings (p-strings). Two p-strings of the same length aresaid to parameterized match (p-match) if one string can be transformed into theother by using a bijection on Σ ∪ Π, with the restriction that the bijection must
be the identity on the constant symbols of Σ. In other words, the bijection maps
any a ∈ Σ to a itself, while symbols of Π can be interchanged. Examples ofapplications of parameterized pattern matching are software maintenance [1, 2],plagiarism detection [3], and RNA structural matching [4].
For the standard pattern matching problem, there exist several data structures that can be obtained by preprocessing the text string so that patternmatching can be performed eﬃciently. The most famous are the suﬃx tree [5]and suﬃx array [6]. These data structures can both be constructed directly in
linear time [5, 7–12], independent of the alphabet size. Most operations on a
suﬃx tree can be eﬃciently simulated with the suﬃx array and several otherauxiliary arrays, including an array containing the lengths of longest common
preﬁxes of the suﬃxes (LCP array), composing an enhanced suﬃx array [13, 14].
The array representation has become more preferable as it requires less memory,and is generally faster to construct and work on, due to memory access locality.
For p-string pattern matching, Baker [2] introduced the parameterized suﬃx
tree (p-suﬃx tree), which is similar in concept to the suﬃx tree. Baker gave anO(n(π + log(π + σ))) time algorithm to construct the p-suﬃx tree for a given
text string, where n is the text length, π = |Π| and σ = |Σ|. Kosaraju [15]proposed an algorithm to construct p-suﬃx trees in O(n(log π + log σ)) time.

2

Both algorithms are based on McCreight’s construction algorithm for standard
suﬃx trees [7]. Shibuya [4] gave an on-line construction algorithm working inO(n(log π + log σ)) time, which is based on Ukkonen’s construction algorithm
for standard suﬃx trees [8]. Given a pattern p of length m, we can compute theset Pocc of all positions of t where the corresponding substring of t p-matches
pattern p in O(m log(π + σ) + |Pocc|) time, using the p-suﬃx tree of a text t.
Concerning the array representation, parameterized suﬃx arrays were considered by Deguchi et al. [16]. The parameterized pattern matching problem
can be solved in O(m log n + |Pocc|) time with a simple binary search, or O(m +log n+|Pocc|)) with a binary search utilizing PLCP information, or O(m log(π +σ) + |Pocc|) time if we consider enhanced p-suﬃx arrays. As with the case ofstandard suﬃx trees and arrays, the array representation is superior in memory
usage and memory access locality. Deguchi et al. presented a linear time algorithm for direct construction of the parameterized suﬃx array and parameterized
LCP (PLCP) array for binary strings. To the best of our knowledge, no eﬃcientalgorithm for direct construction of a parameterized suﬃx array and PLCP array for non-binary strings exist, and the best theoretical worst-case time boundis O(n2 ), using a standard radix sort on strings.
This paper presents a new algorithm for eﬃcient construction of p-suﬃx
arrays and PLCP arrays for non-binary strings. For p-suﬃx array construction,
our algorithm combines any string sorting algorithm with linear time pre- andpost processing. Though we are unable to reduce the theoretical worst case timebound, our algorithm considerably reduces the number of suﬃxes to be sorted
using the string sorting algorithm, hence greatly reducing the running time. For
the PLCP array, we modify the linear time LCP array construction algorithmof [17], so that it can be used for p-strings. However, due to properties of pstrings, it is still open if the theoretical time bound of our algorithm is linear.
Computational experiments show both our algorithms are generally much fasterthan naı̈ve approaches for various texts.

2

Preliminaries

Let Σ and Π be two disjoint ﬁnite sets of constant symbols and parameter
symbols, respectively. An element of (Σ ∪ Π)∗ is called a p-string. The lengthof any p-string s is the total number of constant and parameter symbols in s
and is denoted by |s|. For any p-string s of length n, the i-th symbol is denotedby s[i] for each 1 ≤ i ≤ n, and the substring starting at position i and endingat position j is denoted by s[i : j] for 1 ≤ i ≤ j ≤ n. In particular, s[1 : j]and s[i : n] denote the preﬁx of length j and the suﬃx of length n − i + 1 ofs, respectively. For any two strings s and t, lcp(s, t) denotes the length of thelongest common preﬁx of s and t.
Deﬁnition 1 (Parameterized Matching). Any two p-strings s and t of thesame length m are said to parameterized match (p-match) iﬀ one of the following
conditions hold for every 1 ≤ i ≤ m:

3

1. s[i] = t[i] ∈ Σ,
2. s[i], t[i] ∈ Π, s[i] ̸= s[j] and t[i] ̸= t[j] for any 1 ≤ j < i,3. s[i], t[i] ∈ Π, s[i] = s[i − k] for any 1 ≤ k < i iﬀ t[i] = t[i − k].
We write s ≃ t when s and t p-match.
For example, let Π = {a, b, c}, Σ = {X, Y}, s = abaXabY and t = bcbXbcY.
Observe that s ≃ t.
Let N be the set of non-negative integers. For any non-negative integers
i ≤ j ∈ N , let [i, j] = {i, i + 1, . . . , j} ⊂ N .
Deﬁnition 2. We deﬁne pv : (Σ ∪ Π)∗ → (Σ ∪ N )∗ to be the function suchthat for any p-string s of length n, pv (s) = u where, for 1 ≤ i ≤ n,
if s[i] ∈ Σ,s[i]u[i] = 0
if s[i] ∈ Π and s[i] ̸= s[j] for any 1 ≤ j < i,
i − k if s[i] ∈ Π and k = max{j | s[i] = s[j], 1 ≤ j < i}.
In the running example, pv (s) = 002X24Y with s = abaXabY.
The following proposition is clear from Deﬁnition 2.
Proposition 1. For any p-string s of length n, it holds for any 1 ≤ i ≤ j ≤ nthat pv (s[i : j]) = v[1 : j − i + 1], where v = pv (s[i : n]).
Proposition 2 ([2]). For any two p-strings s and t of the same length, s ≃ t
iﬀ pv (s) = pv (t).
In the running example, we then have s ≃ t and pv (s) = pv (t) = 002X24Y.
We also deﬁne the dual of the pv function, as follows:
Deﬁnition 3. We deﬁne fw : (Σ ∪ Π)∗ → (Σ ∪ N ∪ {∞})∗ to be the function
such that for any p-string s of length n, fw (s) = w where, for 1 ≤ i ≤ n,
if s[i] ∈ Σ,s[i]w[i] = ∞if s[i] ∈ Π and s[i] ̸= s[j] for any i < j ≤ n,k − i if s[i] ∈ Π and k = min{j | s[i] = s[j], i < j ≤ n}.
Here, ∞ denotes a value for which i < ∞ for any i ∈ N . 1
In the running example, fw (s) = 242X∞∞Y with s = abaXabY.
Proposition 3. For any p-string s of length n, it holds for any 1 ≤ i ≤ n thatfw (s[i : n]) = w[i : n], where w = fw (s).
For any p-string s of length n, pv (s) and fw (s) can be computed in O(n)time with extra O(π) space, using a table of size π recording the last position ofeach parameter symbol in the left-to-right (resp. right-to-left) scanning of s [2].
1

In practice, n can be used in place of ∞ as long as we are considering a single p-stringof length n, and its substrings.

4

Problem 1 (P-matching problem). Given any two p-strings t and p of length nand m respectively, n ≥ m, compute Pocc(t, p) = {i | t[i : i + m − 1] ≃ p}.
Proposition 2 implies that Pocc(t, p) = {i | pv (p) = pv (t[i : i + m − 1])}.
Lemma 1 ([18]). Problem 1 on alphabet Σ ∪ Π is reducible in linear time to
Problem 1 on alphabet Π.
Due to the above lemma, in the remainder of the paper, we consider only pstrings in Π ∗ . Then, note that for any p-string s of length n, pv (s) ∈ {[0, n−1]}nand fw (s) ∈ {[1, n − 1] ∪ {∞}}n . We also see that if pv (s)[i] > 0 then fw (s)[i −pv (s)[i]] = pv (s)[i]. Similarly, if fw (s)[i] < n then pv (s)[i + fw (s)[i]] = fw (s)[i].
Let ≼ denote the standard lexicographic ordering on strings of an integeralphabet. To simplify discussions on the end of strings, we assume that for any
p-string s, pv (s)[i] = −1 for any i > |s|.
In this paper, we will consider construction of the following data structures.
Deﬁnition 4 (P-suﬃx Array). For any p-string s ∈ Π n of length n, its psuﬃx array PSAs is an array of length n such that PSAs [i] = j, where pv (s[j : n])is the lexicographically i-th element of {pv (s[k : n]) | 1 ≤ k ≤ n}.
Deﬁnition 5 (PLCP Array). For any p-string s ∈ Π n of length n, its PLCP
array PLCP s is an array of length n such that{−1
if i = 1,
PLCP s [i] =lcp(pv (s[PSA[i − 1] : n]), pv ([s[PSA[i] : n])) if 2 ≤ i ≤ n.
We abbreviate PLCP s as PLCP when clear from the context. The following isa useful auxiliary array that we will use for the construction of PLCP .
Deﬁnition 6 (rank array). For any p-string s ∈ Π n of length n, its rank arrayrank s is an array of length n such that rank s [PSAs [i]] = i, for any 1 ≤ i ≤ n.
We abbreviate rank s as rank when clear from the context. Note that rank s [i]can be computed in linear time from PSAs for all i where 1 ≤ i ≤ n.
Table 1 shows an example of a p-suﬃx array, PLCP array and rank array forthe string s = babbcacaabcb.
The PSA, PLCP , and rank arrays can naturally be used in similar ways as
the suﬃx, LCP, and rank arrays for standard strings. PSA and PLCP arrays canbe constructed by a linear time traversal on the p-suﬃx tree. However, unlike
standard suﬃx arrays and lcp arrays, direct linear time algorithms that do notconstruct the tree as an intermediate data structure are not known, except forthe case of binary alphabets [16].
The main diﬃculty in developing eﬃcient algorithms for constructing PSA
and PLCP is that for any p-string s, a suﬃx pv (s)[i : n] of pv (s) is not necessarilyequal to pv (s[i : n]) of the suﬃx s[i : n]. As an important consequence, for any
p-strings s, t with lcp(pv (s), pv (t)) > 0, pv (s) ≼ pv (t) does not necessarily imply
pv (s[2 : |s|]) ≼ pv (t[2 : |t|]), which is a property essential for eﬃcient construction
algorithms in the standard case.

5
Table 1. PSAt and PLCP t for p-string s = babbcacaabcb.
i PSA[i] PLCP [i] rank[i] 1 2 3 4 5 6 7 8 9 10 11 12 zlen[PSA[i]] type
1
12
-1
9 0
1
A
2
11
1
6 0 0
2
A
3
9
2
12 0 0 0 2
3
B
4
4
4
4 0 0 0 2 2 1 6 4 2
3
B
5
7
2
10 0 0 1 0 4 2
2
B
6
2
6
8 0 0 1 0 4 2 2 1 6 4 2
2
B
7
10
2
5 0 0 22
C
8
6
3
11 0 0 2 1 0 4 2
2
C
9
1
7
3 0 0 2 1 0 4 2 2 1 6 4 2
2
C
10
5
3
7 0 0 2 2 1 0 4 2
2
C
11
8
1
2 0 1 0 0 2
1
C
12
3
5
1 0 1 0 0 2 2 1 6 4 2
1
C3

Algorithm

For our lightweight algorithm, we will use the number of contiguous zeroes in
the preﬁx of each suﬃx pv (s[i : n]), to sort them coarsely.
Deﬁnition 7. For any p-string s of length n, we deﬁne zlen s [i] as the length ofcontiguous zeroes in the preﬁx of pv (s[i : n]) for any 1 ≤ i ≤ n. That is,{ ¯}zlens [i] = max j ¯ pv(s[i : i + j − 1]) = 0j , 1 ≤ j ≤ n − i + 1 .
We abbreviate zlen s as zlen when clear from the context. Note that zlen s [i]can be computed in amortized linear time for all i where 1 ≤ i ≤ n.
3.1

Constructing P-suﬃx Arrayzlen divides the set of suﬃxes s[i : n](1 ≤ i ≤ n) of p-string s into 3 types.
– Type A: those consisting of zeroes only, that is zlen s [i] = |s| − i + 1.
– Type B: those with zlen s [i] < |s|−i+1 and zlen s [i] > pv (s[i : n])[zlen s [i]+1]– Type C: those with zlen s [i] < |s|−i+1 and zlen s [i] = pv (s[i : n])[zlen s [i]+1].
Our algorithm consists of the following steps.
1. Calculate zlen s [i] for all i in linear time and determine its type.
2. Determine the positions of type A suﬃxes using zlen s [i].
3. Coarsely sort all type B and C suﬃxes in linear time by radix sort using
zlen s [i] and the ﬁrst non-zero value pv (s[i : n])[zlen s [i] + 1] in pv (s[i : n]).
4. Determine the positions of the type B suﬃxes using any sorting algorithm.
5. Determine the positions of the remaining type C suﬃxes in linear time.

6

Each step can be calculated in linear time except for Step 4 which depends on
the underlying sort algorithm. We will describe the details of each step below.
First, we determine the positions of the type A suﬃxes (Step 2). Let As
denote the number of type A suﬃxes of s. For the type A suﬃxes, it is obviousthat PSAs [1 : As ] = n, n − 1, . . . , n − As + 1.
For the type B and C suﬃxes (Step 3), they are divided into blocks of suﬃxes
that have the same zlen value and ﬁrst non-zero value. We can determine theorder of these blocks in linear time and space by radix sort, that is, bucket
sort ﬁrst in ascending order of the ﬁrst non-zero value and then in descendingorder of the zlen value. For any suﬃx i, the ﬁrst non-zero value is not greaterthan zlen[i]. Therefore, we can also do this operation by a single bucket sort in∑zlen[i]descending order of t=1 t − pv (s[i : n])[zlen[i] + 1] = zlen[i](zlen[i]+1)− pv (s[i :2n])[zlen[i] + 1]. This alternative method works in linear time and space, as long
= O(n), where z = max {zlen s [i] | 1 ≤ i ≤ n − As }.
as z(z+1)
2
Step 4 is then conducted using any string sorting algorithm within eachtype B block. Note that within a block, it suﬃces to see the order of pv (s[i :n])[zlen s [i] + 2 : n] since they will have a common preﬁx of length zlen s [i] + 1.
Let P SAs denote the intermediate array obtained just after processing Step 4,that is, only the type C suﬃxes are not in position yet. The next lemmas describe
the key properties for sorting these remaining suﬃxes in linear time (Step 5).
Lemma 2. Let s be a p-string of length n. For any i, j (1 ≤ i, j ≤ n − 1), if
fw (s)[i] ≥ fw (s)[j] and pv (s[i + 1 : n]) ≺ pv (s[j + 1 : n]), then pv (s[i : n]) ≺pv (s[j : n]).
Proof. Assume on the contrary that pv (s[i : n]) ≻ pv (s[j : n]). Let l be
lcp(pv (s[i : n]), pv (s[j : n])). Since pv (s[i : n]) ≻ pv (s[j : n]), thenpv (s[i : n])[1 : l] = pv (s[j : n])[1 : l], pv (s[i : n])[l + 1] > pv (s[j : n])[l + 1].
(i) fw (s)[j] > l. Since fw (s)[i] ≥ fw (s)[j], then pv (s[i + 1 : n])[1 : l − 1] =pv (s[j + 1 : n])[1 : l − 1], pv (s[i + 1 : n])[l] > pv (s[j + 1 : n])[l]. We get
pv (s[i + 1 : n]) ≻ pv (s[j + 1 : n]), a contradiction.
(ii) fw (s)[j] = l. By assumption, pv (s[i : n])[l + 1] > pv (s[j : n])[l + 1] =fw (s)[j] = l. However, by Deﬁnition 2, pv (s[i : n])[l + 1] ≤ l, a contradiction.
(iii) fw (s)[j] < l. Since fw (s)[i] = fw (s)[j], then pv (s[i + 1 : n])[1 : l − 1] =pv (s[j + 1 : n])[1 : l − 1], pv (s[i + 1 : n])[l] > pv (s[j + 1 : n])[l]. We get
pv (s[i + 1 : n]) ≻ pv (s[j + 1 : n]), a contradiction.
⊓⊔
Lemma 3. Let s be a p-string of length n. For any i (1 ≤ i ≤ n − 1), if
pv (s[i : n]) is a type C suﬃx, then pv (s[i + 1 : n]) ≺ pv (s[i : n]).
Proof. Assume on the contrary that pv (s[i + 1 : n]) ≻ pv (s[i : n]). Since pv (s[i :n]) is a type C suﬃx, zlen[i + 1] ≥ zlen[i]. Then for some k (zlen[i] + 2 ≤ k ≤n−i+1), pv (s[i+1 : n])[1 : k −1] = pv (s[i : n])[1 : k −1] and pv (s[i+1 : n])[k] >pv (s[i : n])[k]. In addition, it follows from pv (s[i : n])[zlen[i] + 1] = zlen[i] that

7// Initialize://
head[i] = k: min position in type C block with k = zlen[PSA[j]]//block[i] = if(PSA[i]-1 is type C) then zlen[PSA[i]-1] else 0for (i = 1; i < n; i++) {j = block[psa[i]];if (j != 0) {// s[psa[i]-1:n] is type C
psa[head[j]] = psa[i] - 1; // determine its position in block jhead[j]++;// increment head position of block}}
Fig. 1. Algorithm for sorting type C suﬃxes in linear time. Note that the initializationof head and block arrays can be done in linear time.

pv (s[i + 1 : n])[zlen[i] + 1 : n] = pv (s[i : n])[zlen[i] + 2 : n − 1]. Here,pv (s[i : n])[k] = pv (s[i + 1 : n])[k − 1] = pv (s[i : n])[k − 1]
= pv (s[i + 1 : n])[k − 2] = pv (s[i : n])[k − 2]
= · · · = pv (s[i + 1 : n])[zlen[i] + 1] = pv (s[i : n])[zlen[i] + 1] = zlen[i].
Hence pv (s[i + 1 : n])[1 : k − 1] = 0zlen[i] zlen[i]k−1−zlen[i] . This implies that
pv (s[i + 1 : n])[k] ≤ zlen[i] = pv (s[i : n])[k], a contradiction.
⊓⊔
Theorem 1. Let s be a p-string of length n. If the positions of type A and B
suﬃxes are determined, the positions of the remaining type C suﬃxes can be
determined in linear time.
Proof. From Lemma 2, if pv (s[i + 1 : n]) ≺ pv (s[j + 1] : n) and pv (s[i : n]),
pv (s[j : n]) are in the same type C block, we have pv (s[i : n]) ≺ pv (s[j : n])since fw values are equal. Therefore, we scan P SAs in increasing order anddetermine the correct position of type C suﬃx pv (s[i : n]) if the position of
suﬃx pv (s[i + 1 : n]) is already determined. This is guaranteed by Lemma 3,
since the position of suﬃx pv (s[i + 1 : n]) precedes that of pv (s[i : n]). Hence,
we can determine the positions of the type C suﬃxes by running through P SAs
once.
⊓
⊔
Fig. 1 shows our linear time sorting algorithm for type C suﬃxes.
3.2

Constructing PLCP Array

This section considers the construction of PLCP arrays, given the p-suﬃx array.
For standard LCP arrays, Kasai et al. [17] showed a linear time algorithm forits construction, given the suﬃx array. However, the same algorithm cannot beapplied directly to PLCP arrays because of the diﬃculties mentioned at the endof Section 2. In the following, we show some characteristics of PLCP arrays andpropose P-Kasai, a modiﬁed version of the algorithm of [17].
For the type A suﬃxes, it is obvious that PLCP s [1 : As ] = −1, 1, 2, . . . , As −1.
Hence we mainly consider computing PLCP s [i] where As < i ≤ n.

8Lemma 4. Let s be a p-string of length n and li = PLCP s [rank [i]]. For anyi (1 ≤ i < n), if li > 0 then{li+1 ≥ li − 1 if pv (s[j + 1 : n]) ≺ pv (s[i + 1 : n]),lj+1 ≥ li − 1 if pv (s[j + 1 : n]) ≻ pv (s[i + 1 : n]),where j = PSA[rank [i] − 1].
Proof. Since pv (s[j : j +li −1]) = pv (s[i : i+li −1]), then pv (s[j +1 : j +li −1]) =pv (s[i + 1 : i + li − 1]). If pv (s[j + 1 : n]) ≺ pv (s[i + 1 : n]), then for anyk (rank [j + 1] ≤ k ≤ rank [i + 1]),
pv (s[j + 1 : j + li − 1]) = pv (s[PSA[k] : PSA[k] + li − 2]) = pv (s[i + 1 : i + li − 1]).
Hence, li+1 ≥ li − 1. Similarly, if pv (s[j + 1 : n]) ≻ pv (s[i + 1 : n]), we can get
lj+1 ≥ li − 1.
⊓⊔Note that the case of li > 0 and pv (s[j + 1 : n]) ≻ pv (s[i + 1 : n]) does not occur
for LCP arrays, which is the key property for amortized linear time construction
algorithm [17]. In the case for PLCP arrays, for example, we can see in Table 1
that pv (s[2 : 12]) ≺ pv (s[10 : 12]) but pv (s[3 : 12]) ≻ (s[11 : 12]).
A necessary condition for pv (s[j + 1 : n]) ≻ pv (s[i + 1 : n]) is given below:
Lemma 5. Let s be a p-string of length n and li = PLCP s [rank [i]]. For anyi (1 ≤ i < n), if pv (s[j + 1 : n]) ≻ pv (s[i + 1 : n]) then pv (s[i : n])[li + 1] = li ,where j = PSA[rank [i] − 1].
Proof. First, pv (s[j + 1 : n])[1 : li − 1] = pv (s[i + 1 : n])[1 : li − 1], and by
Deﬁnition 2 pv (s[i : n])[li + 1] ≤ li . If we assume pv (s[i : n])[li + 1] < li , thenpv (s[j + 1 : n])[li ] ≤ pv (s[j : n])[li + 1] < pv (s[i : n])[li + 1] = pv (s[i + 1 : n])[li ].
This implies that pv (s[j + 1 : n]) ≺ pv (s[i + 1 : n]), a contradiction.

⊓⊔

Focusing on the case of pv (s[i + 1 : n]) ≺ pv (s[i : n]), we have:
Lemma 6. Let s be a p-string of length n and li = PLCP s [rank [i]]. For anyi (1 ≤ i < n), if pv (s[i : n])[li + 1] = li and pv (s[i + 1 : n]) ≺ pv (s[i : n]) thenzlen[i + 1] ≥ li .
Proof. Assume contrary that zlen[i + 1] < li . Since pv (s[i + 1 : n])[li ] = 0, there
exists m = min{k | 2 ≤ k < li , pv (s[i + 1 : n])[k] ̸= 0}, that is, zlen[i + 1] = m − 1,and then zlen[i] = m. This implies pv (s[i : n]) ≺ pv (s[i+1 : n]), a contradiction. ⊓⊔Lemmas 5 and 6 lead to the next lemma.
Lemma 7. Let s be a p-string of length n and li = PLCP s [rank [i]]. For anyi (1 ≤ i < As − 1), if pv (s[j + 1 : n]) ≻ pv (s[i + 1 : n]) and pv (s[i + 1 : n]) ≺pv (s[i : n]) then{li+1 = As if rank [i + 1] = As + 1 and li > As ,li+1 ≥ liotherwise,
where j = PSA[rank [i] − 1].

9plcp[1] = -1;
for (b = 2; psa[b] == n - b; b++) {plcp[b] = b - 1; // PLCP for type A suffixes}// b = As + 1
k = 1;for (i = 1; i <= n - b + 1; i++) {j = psa[rank[i]-1];
if (plcp[rank[i]] > k)k = plcp[rank[i]];while (pv(s[i:n])[k+1] == pv(s[j:n])[k+1])
k++;plcp[rank[i]] = k;if (rank[j+1] < rank[i+1])k--;// Kasai’s algorithm up to here
else {// below is modification
if (plcp[rank[j+1]] < k - 1)
plcp[rank[j+1]] = k - 1;
if (rank[i+1] < rank[i]) {if (rank[i+1] == b && k > b - 1)
k = b - 1;
} elsek = 1;}}
Fig. 2. Algorithm for constructing PLCP array (P-Kasai).

Proof. It follows from Lemma 5 and 6 that zlen[i+1] ≥ li . If rank [i+1] = As +1,
it is obvious that zlen[PSA[rank [i + 1] − 1]] = zlen[PSA[As ]] = As . In addition if
li > As , then pv (s[1 : As ]) = 0As is a preﬁx of pv (s[i + 1 : n]). Hence li+1 = As .
On the other hand, in the case of rank [i+1] > As +1, we have zlen[PSA[rank [i+1] − 1]] ≥ li , since type B and C suﬃxes are sorted in descending order of zlen.
If rank [i + 1] = As + 1 but li ≤ As , then zlen[PSA[rank [i + 1] − 1]] = As ≥ li .
Hence in either case, zlen[PSA[rank [i + 1] − 1]] ≥ li , and then li+1 ≥ li .
⊓⊔Lemma 7 helps to compute li+1 in the case of pv (s[j + 1 : n]) ≻ pv (s[i + 1 : n]).
Fig. 2 shows our algorithm for constructing PLCP array.

4

Computational Experiments

We compare our algorithms and naive algorithms on randomly generated text,
and some ﬁles taken from the The Canterbury Corpus2 , and those used in [19]3(Lightweight). All experiments were conducted on an Apple Mac Pro (Early2008) with 3.2GHZ dual core Xeons and 18GB of memory, running MacOSX
10.5 Leopard. Programs were written in the C language and compiled with thegcc compiler and -O3 option.
23

http://corpus.canterbury.ac.nz/
http://web.unipmn.it/∼manzini/lightweight/corpus/

10
Table 2. Running times for random strings of length n and alphabet size = 255.
p-suﬃx array
PLCP arrayn
Radix Bucket
Qsort P-Kasai
Naive avg lcp avg zlen %C1024 0.000099 0.000170 0.000710 0.000023 0.000207
23.6
19.4 7.58
2048 0.000241 0.000319 0.001672 0.000050 0.000374
25.5
19.6 7.57
4096 0.000689 0.000778 0.004032 0.000147 0.000595
27.1
19.7 7.66
8192 0.001759 0.001840 0.009391 0.000304 0.001116
28.1
19.6 7.73
16384 0.003840 0.003908 0.018881 0.000629 0.002363
29.0
19.7 7.71
32768 0.009518 0.009440 0.042851 0.001291 0.004697
29.6
19.6 7.73
65536 0.022920 0.022261 0.096403 0.002856 0.010423
30.3
19.7 7.72
131072 0.050810 0.048990 0.201429 0.006450 0.020761
31.0
19.7 7.73
262144 0.124608 0.120097 0.458788 0.015064 0.039021
31.9
19.7 7.72
524288 0.287857 0.276315 0.998540 0.062928 0.083262
33.0
19.7 7.72

Table 2 shows results on random data for various text lengths, and a ﬁxed
alphabet size of 255. Table 3 shows results on random data for various alphabet
sizes and a ﬁxed text length of 1,000,000. Table 4 shows results on various texts
from several corpora. Radix and Bucket denote the two alternatives for thecoarse sorting in Step 3. We use a standard quick sort on strings for the sorting
algorithm of Step 4. Qsort denotes a naive algorithm using a standard quick sorton all suﬃxes. For the PLCP array, we compare the P-Kasai algorithm and anaive algorithm. %C denotes the percentage of type C suﬃxes. The running times
were measured by user time, averaged over 100 and 10 iterations for random
strings and ﬁles, respectively. In the tables, they are presented in second.
Our algorithms are clearly much faster than naive methods except for the
PLCP computation when the average lcp is small.

5

Conclusion and Future Work

Using several characteristics of parameterized suﬃxes, we introduced techniquesto speed up the direct construction of parameterized suﬃx arrays and PLCP
arrays. The worst case time complexity of sorting the suﬃxes is O(n3 ) when using
a standard Quicksort on strings. For example, considering pv (abbaabb . . .) =0013131 . . ., gives one type B block of size n/2 requiring O(n3 ) time. However,since the size of the blocks to be sorted is reduced considerably compared ton, the total time required for our algorithm is much faster than a naı̈ve use of
Quicksort.
From a theoretical viewpoint, a naı̈ve radix sort would give an O(n2 ) timealgorithm. It is an open problem if there exists better worst-case time algorithms
for p-suﬃx array construction. Similarly, for PLCP arrays, the P-Kasai algorithm
runs in O(n2 ) time. However, we do not know if this bound is tight, or if there
exist linear time algorithms for PLCP array construction.

11
Table 3. Running times for random strings of length 1,000,000 and alphabet size π.
p-suﬃx array
PLCP array
π Radix Bucket Qsort P-Kasai Naive avg lcp avg zlen %C
2 0.351 0.327 1.144
0.203 0.124
19.8
1.5 75.0
4 0.387 0.363 0.851
0.228 0.109
11.5
2.2 55.5
8 0.430 0.404 0.839
0.242 0.112
10.7
3.2 40.6
16 0.493 0.459 0.975
0.239 0.121
12.2
4.7 29.4
32 0.522 0.495 1.114
0.225 0.131
15.1
6.8 21.2
64 0.543 0.528 1.346
0.204 0.145
19.4
9.7 15.2
128 0.584 0.572 1.645
0.187 0.161
25.7
13.9 10.8
256 0.633 0.613 2.111
0.170 0.186
34.2
19.7 7.70
512 0.697 0.688 2.708
0.159 0.224
45.1
28.0 5.48
1024 0.754 0.754 3.570
0.147 0.264
61.1
39.8 3.89
2048 0.851 0.825 4.688
0.141 0.360
84.8
56.4 2.75
4096 0.940 0.921 6.309
0.132 0.454 118.6
79.8 1.95
8192 0.984 0.990 8.373
0.127 0.628 165.8
113.1 1.38
16384 1.039 1.068 11.570
0.124 0.864 230.3
160.0 0.978
32768 1.289 1.074 15.510
0.119 1.266 317.0
226.2 0.691
65536 0.967 1.070 21.972
0.115 1.896 430.8
320.0 0.489
131072 0.834 0.992 30.362
0.112 3.058 578.2
453.5 0.345
262144 0.667 0.946 42.425
0.111 5.780 766.4
640.4 0.245
524288 0.509 0.941 58.855
0.105 9.795 1019.7
907.2 0.173

References
1. Baker, B.S.: A program for identifying duplicated code. Computing Science andStatistics 24 (1992) 49–57
2. Baker, B.S.: Parameterized pattern matching: Algorithms and applications. Journal of Computer and System Sciences 52(1) (1996) 28–42
3. Fredriksson, K., Mozgovoy, M.: Eﬃcient parameterized string matching. Information Processing Letters 100(3) (2006) 91–96
4. Shibuya, T.: Generalization of a suﬃx tree for RNA structural pattern matching.
Algorithmica 39(1) (2004) 1–19
5. Weiner, P.: Linear pattern-matching algorithms. In: Proc. of 14th IEEE Ann.
Symp. on Switching and Automata Theory. (1973) 1–11
6. Manber, U., Myers, G.: Suﬃx arrays: a new method for on-line string searches.
SIAM J. Computing 22(5) (1993) 935–948
7. McCreight, E.M.: A space-economical suﬃx tree construction algorithm. Journalof the ACM 23(2) (1976) 262–272
8. Ukkonen, E.: On-line construction of suﬃx trees. Algorithmica 14(3) (1995) 249–
260
9. Farach, M.: Optimal suﬃx tree construction with large alphabets. In: Proc. 38th
Annual Symposium on Foundations of Computer Science. (1997) 137–143
10. Kärkkäinen, J., Sanders, P.: Simple linear work suﬃx array construction. In: Proc.
ICALP’03. Volume 2719 of LNCS. (2003) 943–955
11. Kim, D.K., Sim, J.S., Park, H., Park, K.: Linear-time construction of suﬃx arrays.
In: Proc. CPM’03. Volume 2676 of LNCS. (2003) 186–199
12. Ko, P., Aluru, S.: Space eﬃcient linear time construction of suﬃx arrays. In: Proc.
CPM’03. Volume 2676 of LNCS. (2003) 200–210

12Table 4. Running times for ﬁles from several corpora.

Filep-suﬃx array
PLCP array
Radix Bucket
Qsort P-Kasai
Naivelength avg lcp avg %C
zlen

Artiﬁcial
aaa.txt
0.0060 0.0044 175.3258 0.0023 17.0399 100000 49999.5 1.0 99.9
alphabet.txt 0.0060 0.0040 168.2780 0.0024 16.9446 100000 49999.5 26.0 99.9
random.txt 0.0350 0.0321
0.0947 0.0049 0.0102 100000
17.7 9.6 15.2
Canterbury
alice29.txt
0.0492 0.0477
0.1174 0.0088 0.0163 152089
13.6 5.5 31.0
asyoulik.txt 0.0413 0.0379
0.0896 0.0070 0.0125 125179
13.4 5.9 27.5
cp.html
0.0078 0.0073
0.0175 0.0010 0.0036
24603
18.6 6.2 25.1
ﬁelds.c0.0027 0.0025
0.0062 0.0004 0.0016
11150
18.6 5.2 30.0
grammar.lsp 0.0006 0.0006
0.0016 0.0001 0.0004
3721
13.5 5.0 30.2
lcet10.txt
0.1645 0.1544
0.4040 0.0534 0.0510 426754
15.8 5.6 30.5
plrabn12.txt 0.1862 0.1849
0.4506 0.0728 0.0537 481861
13.6 6.1 29.0
xargs.1
0.0008 0.0007
0.0021 0.0001 0.0004
4227
11.6 6.2 28.6
Large
E.coli2.9639 2.9823
7.0833 1.4862 1.0672 4638690
19.3 2.2 55.9
bible.txt
3.1321 3.0253
6.5019 1.1278 0.9816 4047392
18.0 5.5 31.6
world192.txt 2.0905 2.0194
3.9638 0.6075 0.7444 2473400
31.3 5.9 28.2
Misc.
pi.txt0.4567 0.4529
0.8871 0.2449 0.1174 1000000
11.0 3.6 36.6
Lightweightchr22.dna
31.8458 29.8698 4119.5402 12.6971 249.1254 34553758 1980.9 2.0 59.5
etext998.4958 7.8785 14.1768 1.9445 3.3963 6291456
94.6 5.6 29.7
howto
80.2950 77.1156 151.0006 13.6105 49.7969 39422105 273.8 4.8 34.9

13. Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suﬃx trees with enhanced
suﬃx arrays. Journal of Discrete Algorithms 2(1) (2004) 53–86
14. Kim, D.K., Jeon, J.E., Park, H.: An eﬃcient index data structure with the capabilities of suﬃx trees and suﬃx arrays for alphabets of non-negligible size. In:
Proc. SPIRE’04. Volume 3246 of LNCS. (2004) 138–149
15. Kosaraju, S.: Faster algorithms for the construction of parameterized suﬃx trees.
In: Proc. FOCS’95. (1995) 631–637
16. Deguchi, S., Higashijima, F., Bannai, H., Inenaga, S., Takeda, M.: Parameterized
suﬃx arrays for binary strings. In: Proc. PSC’08. (2008) 84–94
17. Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longestcommon-preﬁx computation in suﬃx arrays and its applications. In: Proc. CPM’01.
Volume 2089 of LNCS. (2001) 181–192
18. Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized
matching. Information Processing Letters 49(3) (1994) 111–115
19. Manzini, G., Ferragina, P.: Engineering a lightweight suﬃx array construction
algorithm. Algorithmica 40 (2004) 33–50