Counting Parameterized Border Arrays
for a Binary Alphabet
Tomohiro I1 , Shunsuke Inenaga2 , Hideo Bannai1 , and Masayuki Takeda1
1

2

Department of Informatics, Kyushu University
Graduate School of Information Science and Electrical Engineering,
Kyushu University
744 Motooka, Nishiku, Fukuoka, 819–0395 Japan.
{tomohiro.i,bannai,takeda}@i.kyushu-u.ac.jp
inenaga@c.csce.kyushu-u.ac.jp

Abstract. The parameterized pattern matching problem is a kind ofpattern matching problem, where a pattern is considered to occur in atext when there exists a renaming bijection on the alphabet with which
the pattern can be transformed into a substring of the text. A parameterized border array (p-border array) is an analogue of a border arrayof a standard string, which is also known as the failure function of theMorris-Pratt pattern matching algorithm. In this paper we present a linear time algorithm to verify if a given integer array is a valid p-border
array for a binary alphabet. We also show a linear time algorithm tocompute all binary parameterized strings sharing a given p-border array.
In addition, we give an algorithm which computes all p-border arrays oflength at most n, where n is a a given threshold. This algorithm runs intime linear in the number of output p-border arrays.

1

Introduction

1.1

Parameterized Matching and Parameterized Border Array

The parameterized matching (p-matching) problem [1] is a kind of string matching problem, where a pattern is considered to occur in a text when there exists a
renaming bijection on the alphabet with which the pattern can be transformed
into a substring of the text. A parameterized string (p-string) is formally anelement of (Π ∪ Σ)∗ , where Π is the set of parameter symbols and Σ the set of
constant symbols. The renaming bijections used in p-matching are the identityon Σ, that is, every constant symbol X ∈ Σ is mapped to X, while symbols inΠ can be interchanged. Parameterized matching has applications in software
maintenance [2, 1], plagiarism detection [3], and RNA structural matching [4],thus it has been extensively studied in the last decade [5–12].
Of various efficient methods solving the p-matching problem, this paper focuses on the algorithm of Idury and Schäffer [13] that solves the p-matchingproblem for multiple patterns. Their algorithm modifies the Aho-Corasick automata [14], replacing the goto and fail functions with the pgoto and pfail functions, respectively. When the input is a single pattern p-string of length m, the2T. I, S. Inenaga, H. Bannai, and M. Takeda

pfail function can be implemented by an array of length m, and we call the arraythe parameterized border array (p-border array) of the pattern p-string, whichis the parameterized version of the border array [15]. The p-border array of agiven pattern can be computed in linear time [13].
1.2

Reverse and Enumerating Problems on Strings

The reverse problem for standard border arrays [15] was first introduced byFraněk et al. [16]. They proposed a linear time algorithm to verify if a given
integer array is the border array of some string. Their algorithm works for bothbounded and unbounded alphabets. Duval et al. [17] proposed a simpler algorithm to solve the same problem in linear time for bounded alphabets.
Moore et al. [18] presented an algorithm to enumerate all border arrays oflength at most n, where n is a given positive integer. They proposed a notionof b-equivalence of strings such that two strings are b-equivalent if they havethe same border array. The lexicographically smallest one of each b-equivalenceclass is called b-canonical string of the class. Their algorithm is also able tooutput all b-canonical strings of length up to a given integer n. Franěk et al. [16]pointed out that the time complexity analysis of [18] is incorrect, and showed a
new algorithm which solves the same problem in O(bn ) time using O(bn ) space,
where bn denotes the number of border arrays of length at most n.
The reverse problem for some other string data structures, such as suffix arrays [19], directed acyclic word graphs [20], directed acyclic subsequencegraphs [21] have been solved in linear time [22, 23]. The problem of enumerating
all suffix arrays was considered in [24]. An algorithm to enumerate all p-distinct
strings was proposed in [18], where two strings are said to be p-distinct if they
do not parameterized-match.
1.3

Our Contribution

This paper considers the reversal of the problem of computing the p-border arrayof a given pattern p-string. That is, given an integer array α, determine if there
exists a p-string whose p-border array is α. In this paper, we present a linear
time algorithm which solves the above problem for a binary parameter alphabet(|Π| = 2). We then consider a more challenging problem: given a positive integern, enumerate all p-border arrays of length at most n. We propose an algorithm
that solves the enumerating problem in O(Bn ) time for a binary parameteralphabet, where Bn is the number of all p-border arrays of length n for a binaryparameter alphabet. We also give a simple algorithm to output all strings whichshare the same p-border array.
A p-border is a dual concept of a parameterized period of a p-string. Apostolico and Giancarlo [11] showed that a complete analogy to the weak periodicity
lemma [25] stands for p-strings over a binary alphabet. Our result reveals yet
another similarity of p-strings over a binary alphabet and standard strings interms of periodicity.

Counting Parameterized Border Arrays for a Binary Alphabet

2Preliminaries

2.1

Parameterized String Matching3

Let Σ and Π be two disjoint finite 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 prefix of length j and the suffix of length n − i + 1 of s,
respectively.
Any two p-strings s and t of the same length m are said to parameterized
match if s can be transformed into t by applying a renaming function f fromthe symbols of s to the symbols of t, such that f is the identity on the constantalphabet. For example, let Π = {a, b, c}, Σ = {X, Y}, s = abcXabY and t =bcaXbcY. We then have s ' t with the renaming function f such that f (a) = b,
f (b) = c, f (c) = a, f (X) = X, and f (Y) = Y. We write s ' t when s and t
p-match.
Amir et al. [5] showed that we have only to consider p-strings over Π when
considering p-matching.
Lemma 1 ([5]). The p-matching problem on alphabet Σ ∪ Π is reducible inlinear time to the p-matching problem on alphabet Π.
2.2

Parameterized Border Arrays

As in the case of standard string matching, we can define the parameterizedborder (p-border) and the parameterized border array (p-border array).
Definition 1. A parameterized border ( p-border) of a p-string s of length n is
any integer j such that 0 ≤ j < n and s[1 : j] ' s[n − j + 1 : n].
For example, the set of p-borders of p-string aabbaa is {4, 2, 1, 0}, since
aabb ' bbaa, aa ' aa, a ' a, and ε ' ε.
Definition 2. The parameterized border array ( p-border array) βs of any pstring s of length n is an array of length n such that βs [i] = j, where j is thelongest p-border of s[1 : i].
For example, the p-border array of p-string aabbaa is [0, 1, 1, 2, 3, 4].
When it is clear from the context, we abbreviate βs as β.
The p-border array βs of p-string s was first explicitly introduced by Idury
and Schäffer [13] as the pfail function, where the pfail function is used in their
Aho-Corasick [14] type algorithm that solves the p-matching problem for multiple patterns. Given a pattern p-string p of length m, the p-border array βp can
be computed in O(m log |Π|) time, and the p-matching problem can be solvedin O(n log |Π|) time for any text p-string of length n.

4

2.3

T. I, S. Inenaga, H. Bannai, and M. Takeda

Problems

This paper deals with the following problems.
Problem 1 (Verifying valid p-border array). Given an integer array α of lengthn, determine if there exists a p-string s such that βs = α.
Problem 2 (Computing all p-strings sharing the same p-border array). Given an
integer array α which is a valid p-border array, compute every p-string s suchthat βs = α.
Problem 3 (Computing all p-border arrays). Given a positive integer n, compute
all p-border arrays of length at most n.
In the following section, we give efficient solutions to the above problems fora binary alphabet, that is, |Π| = 2.

3

Algorithms

This section presents our algorithms which solve Problem 1, Problem 2 andProblem 3 for the case |Π| = 2.
We begin with the basic proposition on p-border arrays.
Proposition 1. For any p-border array β[1..i] of length i ≥ 2, β[1..i − 1] is ap-border array of length i − 1.
Proof. Let s be any p-string such that βs = β. It is clear from Definition 2 thatβs [1..i − 1] is the p-border array of the p-string s[1 : i − 1].
ut
Due to the above proposition, given an integer array α[1..n], we can check if it
is a p-border array of some string of length n by testing each element of α inincreasing order (from 1 to n). If we find any 1 ≤ i ≤ n such that α[1..i] is nota p-border array of length i, then α[1..n] can never be a p-border of length n.
In what follows, we show how to check each element of a given integer array inincreasing order.
For any p-border array β of length n and any integer 1 ≤ i ≤ n, let(β[i]if k = 1,
β k [i] =k−1
β[β[i]] if k > 1 and β k−1 [i] ≥ 1.
It follows from Definition 2 that the sequence i, β[i], β 2 [i], . . . is monotone decreasing to zero, hence finite.
Lemma 2. For any p-string s of length i, {βs1 [i], βs2 [i], . . . , 0} is the set of the
p-borders of s.

Counting Parameterized Border Arrays for a Binary Alphabet

5

Proof. First we show by induction that for every k, 1 ≤ k ≤ k 0 , βsk [i] is a p0
border of s, where k 0 is the integer such that βsk [i] = 0. By Definition 2, βs1 [i]is the longest p-border of s. Suppose that for some k, 1 ≤ k < k 0 , βsk [i] is ap-border of s. Here βsk+1 [i] is the longest p-border of βsk [i]. Let f and g be thebijections such thatf (s[1])f (s[2]) · · · f (s[βsk [i]]) = s[i − βsk [i] + 1 : i],g(s[1])g(s[2]) · · · g(s[βsk+1 [i]]) = s[βsk [i] − βsk+1 [i] + 1 : βsk [i]].
Sincef (g(s[1]))f (g(s[2])) · · · f (g(s[βsk+1 [i]]))= f (s[βsk [i] − βsk+1 [i] + 1])f (s[βsk [i] − βsk+1 [i] + 2]) · · · f (s[βsk [i]])= s[i − βsk+1 [i] + 1 : i],we obtain s[1 : βsk+1 [i]] ' s[i − βsk+1 [i] + 1 : i]. Hence βsk+1 [i] is a p-border of s.
We now show any other j is not a p-border of s. Assume for contrary that j,
βsk+1 [i] < j < βsk [i], is a p-border of s. Let q be the bijection such thatq(s[i − j + 1])q(s[i − j + 2]) · · · q(s[i]) = s[1 : j].
Sinceq(f (s[βsk [i] − j + 1]))q(f (s[βsk [i] − j + 2])) · · · q(f (s[βsk [i]]))= q(s[i − j + 1])q(s[i − j + 2]) · · · q(s[i])= s[1 : j],we obtain s[1 : j] ' s[βsk [i] − j + 1 : βsk [i]]. Hence j is a p-border of s[1 : βsk [i]].
However this contradicts with the definition that βsk+1 [i] is the longest p-borderof s[1 : βsk [i]].
utLemma 3. For any p-string s of length i ≥ 1 and a ∈ Π, every p-border of sa
is an element of the set {βs1 [i] + 1, βs2 [i] + 1, . . . , 1}.
Proof. Assume for contrary that sa has a p-border j + 1 ∈/ {βs1 [i] + 1, βs2 [i] +1, . . . , 1}. Since s[1 : j + 1] ' s[i − j + 1 : i]a, we have s[1 : j] ' s[i − j + 1 : i]and j is a p-border of s. It follows from Lemma 2 that j ∈ {βs1 [i], βs2 [i], . . . , 0}.
This contradicts with the assumption.
utBased on Lemma 2 and Lemma 3, we can efficiently compute the p-border
array βs of a given p-string s. Also, our algorithm to solve Problem 1 is basedon these lemmas. Note that Proposition 1, Lemma 2 and Lemma 3 hold for
p-strings over Π of arbitrary size.
In the sequel we show how to select m ∈ {βs1 [i] + 1, βs2 [i] + 1, . . . , 1} such thatβs [1..i]m is a valid p-border array of length i + 1. The following proposition,lemmas and theorems hold for a binary parameter alphabet, |Π| = 2.
For p-border arrays of length at most 2, we have the next proposition.

6

T. I, S. Inenaga, H. Bannai, and M. Takeda
i
s

a

f
βh-1[i]+1gfβh [i]+1

Fig. 1. Illustration for Lemma 5.

Proposition 2. For any p-string s of length 1, βs [1] = 0. For any p-string s0of length 2, βs0 [2] = 1.
Proof. Let Π = {a, b}. It is clear that the longest p-border of a and b is 0.
The p-strings of length 2 over Π are aa, ab, ba, and bb. Obviously the longest
p-border of each of them is 1.
ut
For p-border arrays of length more than 2, we have the following lemmas.
Lemma 4. For any p-string s ∈ Π ∗ , if j ≥ 2 is a p-border of sa with a ∈ Π,
then j is not a p-border of sb, where b ∈ Π − {a}.
Proof. Assume for contrary that j is a p-border of sb. Then, let f and g be thebijections on Π such thatf (s[1])f (s[2]) · · · f (s[j]) = s[i − j + 2 : i]a,g(s[1])g(s[2]) · · · g(s[j]) = s[i − j + 2 : i]b.
We get from f (s[1])f (s[2]) · · · f (s[j−1]) = s[i−j+2 : i] = g(s[1])f (s[2]) · · · g(s[j−1]) that f and g are the same bijections. However, f (s[j]) = a 6= b = g(s[j])implies that f and g are different bijections, a contradiction. Hence j is not ap-border of sb.
ut
Lemma 5. For any p-string s of length i, if βs [βsh−1 [i] + 1] = βsh [i] + 1 andβsh−1 [i] + 1 is a p-border of sa with a ∈ Π, then βsh [i] + 1 is a p-border of sa.
(See also Fig. 1.)
Proof. Let f and g be the bijections on Π such thatf (s[1])f (s[2]) · · · f (s[βsh−1 [i] + 1]) = s[i − βsh−1 [i] + 1 : i]a,g(s[1])g(s[2]) · · · g(s[βsh [i] + 1]) = s[βsh−1 [i] − βsh [i] + 1 : βsh−1 [i] + 1].
Since
f (g(s[1]))f (g(s[2])) · · · f (g(s[βsh [i] + 1]))= f (s[βsh−1 [i] − βsh [i] + 1])f (s[βsh−1 [i] − βsh [i] + 2]) · · · f (s[βsh−1 [i] + 1])= s[i − βsh [i] + 1 : i]a,Counting Parameterized Border Arrays for a Binary Alphabet

7

i
s

a

f
βh-1[i]+1qfβh [i]
q

f

q

f

a

b

Fig. 2. Illustration for Lemma 6.

we obtain s[1 : βsh [i] + 1] ' s[i − βsh [i] + 1 : i]a. Hence βsh [i] + 1 is a p-border ofsa.
utLemma 6. For any p-string s of length i, if βs [βsh−1 [i] + 1] 6= βsh [i] + 1 andβsh−1 [i] + 1 is a p-border of sa with a ∈ Π, then βsh [i] + 1 is a p-border of sb suchthat b ∈ Π − {a}. (See also Fig. 2.)
Proof. Let f and g be the bijections on Π such thatf (s[1])f (s[2]) · · · f (s[βsh−1 [i] + 1]) = s[i − βsh−1 [i] + 1 : i]a,q(s[1])q(s[2]) · · · q(s[βsh [i]]) = s[βsh−1 [i] − βsh [i] + 1 : βsh−1 [i]].
Because βs [βsh−1 [i] + 1] 6= βsh [i] + 1, we know that q(s[βsh [i] + 1]) 6= s[βsh−1 [i] + 1].
Since f (s[βsh−1 [i] + 1]) = a and Π = {a, b}, f (q(s[βsh [i] + 1])) = b. Hence βsh [i] + 1
is a p-border of sb.
ut
The following is a key lemma to solving our problems.
Lemma 7. For any p-border array β of length i ≥ 2, β[1..i]m1 and β[1..i]m2
are the p-border arrays of length i + 1, where m1 = β[i] + 1 and

l−1
l
0

β l [i] + 1 if β[β [i] + 1] 6= β [i] + 1 for some 1 < l < k andm2 =β[β h−1 [i] + 1] = β h [i] + 1 for any 1 < h < l,1otherwise,0

where k 0 is the integer such that β k [i] = 0.
Proof. Consider any p-string s of length i such that βs = β. By definition, there
exists a bijection f on Π such that f (s[1])f (s[2]) · · · f (s[β[i]]) = s[i − β[i] + 1 : i].
Let a = f (s[β[i]+1]). Then f (s[1])f (s[2]) · · · f (s[β[i]])f (s[β[i]+1]) = s[i−β[i]+1 :8

T. I, S. Inenaga, H. Bannai, and M. Takeda

Algorithm 1: Algorithm to solve Problem 1
Input: α[1..n] : a given integer array
Output: return whether α is a valid p-border array or not
1 if α[1..2] 6= [0, 1] then return invalid;
2 for i = 3 to n do
3
if α[i] = α[i − 1] + 1 then continue;4d0 ← α[i − 1];5d ← α[d0 ];6while d > 0 & d + 1 = α[d0 + 1] do
7
d0 ← d;8d ← α[d0 ];9if α[i] = d + 1 then continue;
10
return invalid;
11 return valid;i]a. Note that β[1..i](β[i] + 1) is the p-border array of sa because sa can haveno p-borders longer than β[i] + 1.
It follows from Lemma 5 that β h [i]+1 is a p-border of sa. Then, by Lemma 6,lβ [i] + 1 is a p-border of sb. Since β h [i] ≥ 1, by Lemma 4, β h [i] + 1 is not a pborder of sb. Hence β l [i] + 1 is the longest p-border of sb.
ut
We are ready to state the following theorem.
Theorem 1. Problem 1 can be solved in linear time for a binary parameteralphabet.
Proof. Algorithm 1 describes the operations to solve Problem 1. Given an integer
array of length n, the algorithm first checks if α[1..2] = [0, 1] due to Proposition 2.
If α[1..2] = [0, 1], then for each i = 3, . . . , n (in increasing order) the algorithm
checks whether α[i] satisfies one of the conditions of Lemma 7.
The time analysis is similar to that of Theorem 2.3 of [16]. In each iterationof the for loop, the value of d0 increases by at most 1. However, each executionof the while loop decreases the value of d0 by at least 1. Hence the total time
cost of the for loop is O(n).
utTheorem 2. Problem 2 can be solved in linear time for a binary parameteralphabet.
Proof. It follows from Proposition 2 that the p-border array of all p-string oflength 2 (aa, ab, ba, and bb) is [0, 1]. By Proposition 1, for any p-border arrayβ[1..n] with n ≥ 2, we have β[1..2] = [0, 1]. Hence each p-border array β[1..n]with n ≥ 2 corresponds to exactly four p-strings each of which begins withaa, ab, ba, and bb, respectively. Algorithm 2 is an algorithm to solve Problem 2.
Technically xaa can be computed by saa [β[i]] xor saa [β[i]+1] xor saa [i] on binaryalphabet Π = {0, 1}. Hence this counting algorithm works in linear time.
utCounting Parameterized Border Arrays for a Binary Alphabet

9

Algorithm 2: Algorithm to compute all p-strings sharing the same pborder array
Input: β[1..n] : a p-border array
Output: all p-strings sharing the same p-border array β[1..n]
1 saa ← aa; sab ← ab; sbb ← bb; sba ← ba;
2 for i = 3 to n do
3
Let f be the bijection on Π s.t. f (saa [β[i]]) = saa [i];4Let g be the bijection on Π s.t. g(sab [β[i]]) = sab [i];5xaa ← f (saa [β[i] + 1]); xab ← g(sab [β[i] + 1]);6xaa ← y ∈ Π − {xaa }; xab ← z ∈ Π − {xab };7if β[i] = β[i − 1] + 1 then8saa [i] ← xaa ; sab [i] ← xab ;9sbb [i] ← xaa ; sba [i] ← xab ;
10
else
11
saa [i] ← xaa ; sab [i] ← xab ;12sbb [i] ← xaa ; sba [i] ← xab ;13end
14 Output: saa [1 : n], sab [1 : n], sbb [1 : n], sba [1 : n]

(0)
(1)
(1)
(1)

(2)
(2)

(1)

(3)

Fig. 3. The tree T4 which represents all p-border arrays of length at most 4 for a binaryalphabet.

We now consider Problem 3. By Proposition 1 and Lemma 7, computing all
p-border arrays of length at most n can be accomplished using a rooted tree
structure Tn of height n − 1. Each node of Tn of height i − 1 corresponds to an
integer j such that j is the longest p-border of some p-string of length i overa binary alphabet, hence the path from the root to that node represents the
p-border array of the p-string. Fig. 3 represents T4 .
Theorem 3. Problem 3 can be solved in O(Bn ) time for a binary parameteralphabet, where Bn denotes the number of p-border arrays of length n.
Proof. Proposition 2 and Lemma 7 imply that every internal node of Tn of heightat least 1 has exactly two children. Hence the total number of nodes of Tn isO(Bn ). We compute Tn in a depth-first manner. Algorithm 3 shows a functionthat computes the children of a given node of Tn . It is not difficult to see that

10

T. I, S. Inenaga, H. Bannai, and M. Takeda

Algorithm 3: Function to compute the children of a node of Tn
Input: i : length of the current p-border array, 2 ≤ i ≤ nResult: compute the children of the current node// β[1..n] is allocated globally and β[1..i] represents the current
p-border array.
1 function getChildren(i)2 if i = n then return ;3 β[i + 1] ← β[i] + 1;
4 report β[i + 1];
5 getChildren(i + 1);
0
6 d ← β[i];07 d ← β[d ];0
8 while d > 0 & d + 1 = β[d + 1] do
09d ← d;10d ← β[d0 ];11 β[i + 1] ← d + 1;
12 report β[i + 1];
13 getChildren(i + 1);
14 return ;each child of a given node can be computed in amortized constant time. Hence
Problem 3 can be solved in O(Bn ) time for a binary parameter alphabet.
ut
We remark that if each p-border array in Tn can be discarded after it is generated,then we can compute all p-border arrays of length at most n using O(n) space.
Since every internal node of Tn of height at least 1 has exactly two children andthe root has one child, Bn = 2n−2 for n ≥ 2. Thus the space requirement can be
reduced to O(log Bn ).

4

Conclusions and Open Problems

A parameterized border array (p-border array) is a useful data structure forparameterized pattern matching. In this paper, we presented a linear time algorithm which tests if a given integer array is a valid p-border array for a binaryalphabet. We also gave a linear time algorithm to compute all binary p-strings
that share a given p-border array. Finally, we proposed an algorithm which computes all p-border arrays of length at most n, where n is a given threshold. Thisalgorithm works in O(Bn ) time, where Bn denotes the number of p-border arraysof length n for a binary alphabet.
Problems 1,2, and 3 are open for a larger alphabet. To see one of the reasonsof why, we show that Lemma 4 does not hold for a larger alphabet. Consider
a p-string s = abac over Π = {a, b, c}. Observe that βs = [0, 1, 2, 2]. Althoughβs [4] = 2 is a p-border of abac, it is also a p-border of another p-string ababsince ab ' ab. Hence Lemma 4 does not hold if |Π| ≥ 3.
Our future work also includes the following:Counting Parameterized Border Arrays for a Binary Alphabet

11– Verify if a given integer array is a parameterized suffix array [12].
– Compute all parameterized suffix arrays of length at most n.
In [12], a linear time algorithm which directly constructs the parameterized suffix
array for a given binary string was proposed. This algorithm might be used asa basis for solving the above problems regarding parameterized suffix arrays.

References
1. Baker, B.S.: Parameterized pattern matching: Algorithms and applications. Journal of Computer and System Sciences 52(1) (1996) 28–42
2. Baker, B.S.: A program for identifying duplicated code. Computing Science andStatistics 24 (1992) 49–57
3. Fredriksson, K., Mozgovoy, M.: Efficient parameterized string matching. Information Processing Letters 100(3) (2006) 91–96
4. Shibuya, T.: Generalization of a suffix tree for RNA structural pattern matching.
Algorithmica 39(1) (2004) 1–19
5. Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized
matching. Information Processing Letters 49(3) (1994) 111–115
6. Baker, B.S.: Parameterized pattern matching by Boyer-Moore-type algorithms.
In: Proc. 6th annual ACM-SIAM Symposium on Discrete Algorithms (SODA’95).
(1995) 541–550
7. Kosaraju, S.: Faster algorithms for the construction of parameterized suffix trees.
In: Proc. 36th Annual Symposium on Foundations of Computer Science (FOCS’95).
(1995) 631–637
8. Hazay, C., Lewenstein, M., Tsur, D.: Two dimensional parameterized matching.
In: Proc. 16th Annual Symposium on Combinatorial Pattern Matching (CPM’05).
Volume 3537 of Lecture Notes in Computer Science. (2005) 266–279
9. Hazay, C., Lewenstein, M., Sokol, D.: Approximate parameterized matching. ACM
Transactions on Algorithms 3(3) (2007) Article No. 29.
10. Apostolico, A., Erdös, P.L., Lewenstein, M.: Parameterized matching with mismatches. Journal of Discrete Algorithms 5(1) (2007) 135–140
11. Apostolico, A., Giancarlo, R.: Periodicity and repetitions in parameterized strings.
Discrete Applied Mathematics 156(9) (2008) 1389–1398
12. Deguchi, S., Higashijima, F., Bannai, H., Inenaga, S., , Takeda, M.: Parameterizedsuffix arrays for binary strings. In: Proc. The Prague Stringology Conference ’08(PSC’08). (2008) 84–94
13. Idury, R.M., Schäffer, A.A.: Multiple matching of parameterized patterns. Theoretical Computer Science 154(2) (1996) 203–224
14. Aho, A.V., Corasick, M.J.: Efficient string matching: An aid to bibliographic
search. Communications of the ACM 18(6) (1975) 333–340
15. Morris, J.H., Pratt, V.R.: A linear pattern-matching algorithm. Technical Report
Report 40, University of California, Berkeley (1970)
16. Franek, F., Gao, S., Lu, W., Ryan, P.J., Smyth, W.F., Sun, Y., Yang, L.: Verifying aborder array in linear time. J. Combinatorial Math. and Combinatorial Computing
42 (2002) 223–236
17. Duval, J.P., Lecroq, T., Lefevre, A.: Border array on bounded alphabet. Journalof Automata, Languages and Combinatorics 10(1) (2005) 51–60

12

T. I, S. Inenaga, H. Bannai, and M. Takeda

18. Moore, D., Smyth, W., Miller, D.: Counting distinct strings. Algorithmica 23(1)(1999) 1–13
19. Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches.
SIAM J. Computing 22(5) (1993) 935–948
20. Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.:
The smallest automaton recognizing the subwords of a text. Theoretical Computer
Science 40 (1985) 31–55
21. Baeza-Yates, R.A.: Searching subsequences (note). Theoretical Computer Science
78(2) (1991) 363–376
22. Duval, J.P., Lefebvre, A.: Words over an ordered alphabet and suffix permutations.
Theoretical Informatics and Applications 36 (2002) 249–259
23. Bannai, H., Inenaga, S., Shinohara, A., Takeda, M.: Inferring strings from graphs
and arrays. In: Proc. 28th International Symposium on Mathematical Foundationsof Computer Science (MFCS 2003). Volume 2747 of Lecture Notes in Computer
Science. (2003) 208–217
24. Schürmann, K.B., Stoye, J.: Counting suffix arrays and strings. Theoretical Computer Science 395(2-1) (2008) 220–234
25. Lyndon, R.C., Schützenberger, M.P.: The equation aM = bN cP in a free group.
Michigan Math. J. 9(4) (1962) 289–298