Two-Dimensional Periodicity in Rectangular Arrays.
String matching is rich with a variety of algorithmic tools. In contrast, multidimensional matching has had a rather sparse set of techniques. This paper presents a new algorithmic technique for two-dimensional matching: periodicity analysis.  Its strength appears to lie in the fact that it is inherently two-dimensional.Periodicity in strings has been used to solve string matching problems. Multidimensional periodicity, however, is not as simple as it is in strings and was not formally studied or used in pattern matching. In this paper, we define and analyze two-dimensional periodicity in rectangular arrays. One definition of string periodicity is that a periodic string can self-overlap in a particular way. An analogous concept is true in two dimensions. The self-overlap vectors of a rectangle generate a regular pattern of locations where the rectangle may originate. Based on this regularity, we define four categories of periodic arrays--- nonperiodic, lattice periodic, line periodic, and radiant periodic---and prove theorems about the properties of the classes. We give serial and parallel algorithms that find all locations where an overlap originates. In addition, our algorithms find a witness proving that the array does not self-overlap in any other location. The serial algorithm runs in time O(m2) (linear time) when  the alphabet size is finite, and in O(m2log m) otherwise.  The parallel algorithm runs in time O(log m) using O(m2) CRCW processors.
Introduction
String matching is a field rich with a variety of algorithmic ideas. The early string matching
algorithms were mostly based on constructing a pattern automaton and subsequently using it
to find all pattern appearances in a given text ([KMP-77, AC-75, BM-77]). Recently developed
algorithms [G-85, V-85, V-91] use periodicity in strings to solve this classic string matching problem.
Lately, there has been interest in various two-dimensional approximate matching problems, largely
motivated by low-level image processing ([KS-87, AL-91, AF-91, ALV-90]). Unlike string matching,
the methods for solving multidimensional matching problems are scant. This paper adds a new
algorithmic tool to the rather empty tool chest of multidimensional matching techniques: two-dimensional
periodicity analysis.
String periodicity is an intuitively clear concept and the properties of a string period are simple
and well understood. Two-dimensional periodicity, though, presents some difficulties. Periodicity
in the plane is easy to define. However, we seek the period of a finite rectangle. We have chosen
to concentrate on a periodicity definition that implies the ability for self-overlap. In strings such
an overlap allows definition of a smallest period whose concatenation produces the entire string.
The main contribution of this paper is showing that for rectangles also, the overlap produces a
"smallest unit" and a regular pattern in which it appears in the array. The main differences are
that this "smallest unit" is a vector rather than a sub-block of the array, and that the pattern is
not a simple concatenation. Rather, based on the patterns of vectors that can occur, there are four
categories of array periodicity: non-periodic, line periodic, radiant periodic and lattice periodic. As
in string matching this regularity can be exploited.
The strength of periodicity analysis appears to lie in the fact that it is inherently a two-dimensional
technique whereas most previous work on two-dimensional matching has reduced the matrix problem
to a problem on strings and then applied one-dimensional string matching methods. The
two dimensional periodicity analysis has already proven useful in solving several multi-dimensional
matching problems [ABF-94a, ABF-93, ABF-94b, KR-94]. We illustrate with two examples.
The original motivation for this work was our research in image preserving compression. We wanted
to solve the following problem: Given a two-dimensional pattern P and a two-dimensional text T
which has been compressed, find all occurrences of P in T without decompressing the text. The goal
is a sublinear algorithm with respect to the size of the original uncompressed text. Some initial
success in this problem was achieved in [ALV-90], but their algorithm, being automaton based,
seems to require a large amount of decompression. In [AB-92b, ABF-94b], we used periodicity to
find the first optimal pattern matching algorithm for compressed two-dimensional texts.
Another application is the two-dimensional exact matching problem. Here the text is not com-
pressed. Baker [B-78] and, independently, Bird [Bi-77] used the Aho and Corasick [AC-75] dictionary
matching algorithm to obtain a O(n 2 log j\Sigmaj) algorithm for this problem. This algorithm is
automaton based and therefore the running time of the text scanning phase is dependent on the
size of the alphabet. In [ABF-94a] we used periodicity analysis to produce the first two dimensional
exact matching algorithm with a linear time alphabet independent text scanning phase.
Since the work presented here first appeared [AB-92a], the analysis of radiant periodic patterns
has been strengthened [GP-92, RR-93], and periodicity analysis has additionally proven useful in
providing optimal parallel two dimensional matching algorithms [ABF-93, CCG+93], as well as in
solving a three dimensional matching problem [KR-94].
This paper is organized as follows. In Section 2, we review periodicity in strings and extend this
notion to two dimensions. In Section 3, we give formal definitions, describe the classification scheme
for the four types of two-dimensional periodicity, and prove some theorems about the properties
of the classes. In Section 4 we present serial and parallel algorithms for detecting the type of
periodicity in an array. The complexity of the serial algorithm is O(m 2 ) (linear time) when the
alphabet size is finite, and O(m 2 log m) otherwise. The parallel algorithm runs in time O(log m)
with O(m 2 ) CRCW processors. In addition to knowing where an array can self overlap, knowing
where it can not and why is also useful. If an overlap is not possible, then the overlap produces
some mismatch. Our algorithms find a single mismatch location or witness for each self overlap
that fails.
2 Periodicity in strings and arrays
In a periodic string, a smallest period can be found whose concatenation generates the entire string.
In two dimensions, if an array were to extend infinitely so as to cover the plane, the one-dimensional
notion of a period could be generalized to a unit cell of a lattice. But, a rectangular array is not
infinite and may cut a unit cell in many different ways at its edges.
Instead of defining two-dimensional periodicity on the basis of some subunit of the array, we instead
use the idea of self-overlap. This idea applies also to strings. A string w is periodic if the longest
prefix p of w that is also a suffix of w is at least half the length of w. For example, if
abcabcabcabcab, then abcabcab and since p is over half as long as w, w is periodic. This
definition implies that w may overlap itself starting in the fourth position.
The preceding idea easily generalized to two dimensions as illustrated in figure 1.
A be a two-dimensional array. Call a prefix of A a rectangular subarray that
contains one corner of A. (In the figure, the upper left corner.) Call a suffix of A a rectangular
subbarray that contains the diagonally opposite corner of A (In the figure, the lower right corner).
We say A is periodic if the largest prefix that is also a suffix has dimensions at least as large as
some fixed percentage d of the dimensions of A.
In the figure, if d - 5, then A is periodic. As with strings, if A is periodic, then A may overlap
itself if the prefix of one copy of A is aligned with the suffix of a second copy of A. Notice that
both the upper left and lower left corners of A can define prefixes, giving A two directions in which
it can be periodic. As we will describe in the next section, the classification of periodicity type for
A is based on whether it is periodic in either or both of these directions.
a

Figure

1:
a) A periodic pattern. b) A suffix matches a prefix.
3 Classifying arrays
Our goal here is classifying an array A into one of four periodicity classes. For clarity of presentation
we concentrate on square arrays. We later show how to generalize all results to rectangles. We
begin with some definitions of two-dimensional periodicity and related concepts (figure 2).
be an m \Theta m square array. Each element of A contains
a symbol from an alphabet \Sigma. A subarray of A is called a block. Blocks are designated by their
first and last row and column. Thus, the block A[0::m \Gamma is the entire array. Each corner
of A defines a quadrant. Quadrants are labeled counterclockwise from upper left, quadrants I , II ,
III and IV . Each quadrant has size q where 1 - q - d me. (Quadrants may share part of a row
or column). Quadrant I is the block 1]. The choice of q may depend on the
application. For this paper,
Definition 3 Suppose we have two copies of A, one directly on top of the other. The copies are
said to be in register because some of the elements overlap (in this case, all the elements) and
overlapping elements contain the same symbol. If the two copies can be repositioned so that A[0; 0]
overlaps and the copies are again in register, then we say that the array is
quadrant I symmetric, that A[r; c] is a quadrant I source and that vector c~x is a quadrant
I symmetry vector. Here, ~y is the vertical unit vector in the direction of increasing row index and
~x is the horizontal unit vector in the direction of increasing column index. If the two copies can
be repositioned so that A[m \Gamma and the copies are again in
register, then we say that the array is quadrant II symmetric, that A[r; c] is a quadrant II source
and that c~x is a quadrant II symmetry vector.
c
a
quadrant I source
quadrant II source
quadrant I symmetry vector
quadrant II symmetry vector
II III
IV
I

Figure

2:
Two overlapping copies of the same array.
a) A quadrant I source. b) A quadrant II source. c) The symmetry vectors.
Analagous definitions exist for quadrants III and IV , but by symmetry, if ~v is a quadrant III(IV )
symmetry vector, then \Gamma~v is a quadrant I(II) symmetry vector. We will usually indicate a vector
c~x by the ordered pair (r; c). Note that symmetry vector (r; c) defines a mapping between
identical elements, that is, (r; c) is a symmetry vector iff A[i;
elements are defined. In particular, if (r; c) is a symmetry vector, then it maps the block A[i::j; k::l]
to the identical block A[i
In the remainder of this paper, we use the terms source and symmetry vector interchangeably.
Definition 4 The length of a symmetry vector is the maximum of the absolute values of its coef-
ficients. The shortest quadrant I (quadrant II) vector is the smallest one in lexicographic order
first by row and then by column (first by column and then by absolute value of row). The basis
vectors for array A are the shortest quadrant I vector (r 1
and the shortest quadrant II
vector any). If the length of a symmetry vector is ! p where me then the vector is
periodic.
We are now ready to classify a square array A into one of four periodicity classes based on the
presence or absence of periodic vectors in quadrants I and II . Following the classification we prove
some theorems about the properties of the classes. In Section 4 we present algorithms for finding
all the sources in an array.
array.
The four classes of two-dimensional periodicity are (figures 3 - 6):
The array has no periodic vectors.
ffl Lattice periodic - The array has periodic vectors in both quadrants. All quadrant I sources
which occur in quadrant I fall on the nodes of a lattice which is defined by the basis vectors.
The same is true for quadrant II sources in quadrant II . Specifically, let ~v 1
) be the periodic basis vectors in quadrants I and II respectively. Then, an
element in quadrant I is a quadrant I source iff it occurs at index A[ir 1
Lattice periodic array.
for integers i; j. An element in quadrant II is a quadrant II source iff it occurs at index
for integers -.
ffl Line periodic - The array has a periodic vector in only one quadrant and the sources in that
quadrant all fall on one line.
ffl Radiant periodic-This category is identical to the line periodic category, except that in the
quadrant with the periodic vector, the sources fall on several lines which all radiate from the
quadrant's corner. We do not describe the exact location of the sources for this class, but see
[GP-92] for a detailed analysis of the source locations.
Next, we prove some theorems about the properties of the classes. All the theorems are stated in
terms of square arrays for clarity. At the end of the theorems we explain how they can be modified
to apply to any n \Theta m rectangular array.
Line periodic array.
In Lemmas 1-3, we establish the fact that if we have symmetry vectors for both quadrants I and II ,
and they meet a pair of constraints on the sum of their coefficients, then every linear combination
of the vectors defines another symmetry vector.
are symmetry vectors from quadrants I and II respectively, and
is either a quadrant I symmetry vector
or a quadrant II symmetry vector (r 1
Proof: We prove for the case r 1 - jr 2 j. The proof for the other case is similar. We show that
) is a quadrant I source.
O
O
III
O
O
O
O
O
O
O
O
I IV
II

Figure

Radiant periodic array. Three non-colinear sources are starred.
First, by the constraint on the c i , the fact that r 2 is negative and the assumption that r 1 - jr 2 j,
S is an element of A. Next, we show via two pairs of mappings that the quadrant I prefix block
is identical to the suffix block A[r 1
First
maps the resultant block to block A[r 1
Second
maps the resultant block to A[m
are two quadrant k symmetry vectors
and c 1
is also a quadrant k symmetry vector.
Proof: We prove for quadrant I . The proof for the other quadrant is similar. We show that
) is a quadrant I source.
First, by the restraints on the r i and the c i , S is an element of A. Next, by a pair of mappings, we
show that the quadrant I prefix block is identical to the
suffix block A[r 1
Recall that both r 1
and r 2
are postive.
First mapping: (r 1
maps the block
\Gamma 1] to the block
maps the resultant block to the block
Lemma 3 If ~v 1
are symmetry vectors from quadrants I and II respec-
tively, and c 1
is an element of A, (ir 1
) is a quadrant I symmetry vector. Similarly, for all - such
that
is an element of A, (-r 1
) is a quadrant II symmetry
vector.
Proof: We prove for vector (ir 1
equivalent to source S
The proof for the other vector is similar. Consider the lattice of elements in A defined by the
quadrant I and II vectors and with one element at A[0; 0]. (The lattice elements correspond
exactly to the elements S i;j .) Consider the line l that extends from element A[0; 0] through elements
We prove the lemma only for those lattice elements on or to the right of l. The
remaining elements are treated similarly.
Case 1: S i;0 on line l. By induction on i. For S 1;0
) is a symmetry vector by
hypothesis. Now, assume that (ir 1
) is a symmetry vector. For S
are both quadrant I symmetry vectors, by Lemma
) is a quadrant I
symmetry vector.
Case 2: S i;j j - 1 to the right of line l. Elements S i;j fall on lines l j which are parallel to line l. We
show that the uppermost element S i;j is a source. By application of Lemma 2, as in Case
the remaining sources on l j are established.
Consider a cell of the lattice with sides (r 1
corners
with S the
uppermost lattice element on line l j (figure 6):
(j
(j
(j
(j
The following are always true:
A
l
l 0

Figure

7:
A candidate source S in lemma 3. Here jr
is not an element of A. Otherwise e 2
- not S - is the top element on its line.
is an element of A. Otherwise S is not in A, S is not to the right of line l or r 1
Two possibilities remain. Either e 1
is an element of A or it is not. Our proof is by induction on i
and j. For the base cases we use ~v 1
which is either
a quadrant I vector (r 1 - jr 2 j) or a quadrant II vector (r 1
Subcase A: r 1
j.
is not an element of A. By the induction hypothesis, ~v e 4
is a symmetry
vector. Since e 1
is not on A, r e 4
. That is, the row coefficient in ~v e 4
is smaller than the
row coefficient in ~v 1:
Apply Lemma 1 to ~v e 4
and ~v 2
and S is a source.
is an element of A. By the induction hypothesis, ~v e 1
is a quadrant I symmetry
vector. From the base case, ~v 3
is a quadrant I symmetry vector. Apply Lemma 2
to ~v e 1
and ~v 3
and S is a source.
Subcase B: r 1
is not an element of A. Impossible, else S is not in A or S is not right of l.
is an element of A. Note that S is above row r 1
or else e 2
is on the array. The vector
is a quadrant II symmetry vector (because r e 2
is negative) by application
of Subcase A to quadrant II . Now, r e 2
=(the row index of S)- 0 so r 1
or jr e 2
By hypothesis, r 1
Apply Lemma 2 to ~v 1
and ~v e 2
and S is a
source. 2
The proof of Theorem 1 is simplified by the following easily proven observation.
) be symmetry vectors from quadrants I and II respectively,
and c 1
let L be an infinite lattice of points on the xy-plane also
with basis vectors (r
). If we put one copy of A on each lattice point by aligning
element A[0; 0] with the lattice point, then the copies are in register and completely cover the plane.
The next Lemma establishes that for a given lattice of elements in A, an element not on the lattice
has a shorter vector to some lattice point than the corresponding basis vector for the lattice. (Note
that a simplified version of the proof appeared in [GP-92] and we use essentially that same proof
here.)

Figure

8:
One of the vectors from e 1
to S or S to e 2
is a quadrant I vector shorter than ~v 1
Lemma 4 Let L be an infinite lattice in the xy-plane with basis vectors ~v 1
(quadrants I and II symmetry vectors respectively) where all the r i and c i are integers. Then, for
any point that is not a lattice element, where x and y are integers, there exists a lattice
point e such that the vector ~v from e to S (or S to e) is a quadrant I vector shorter than ~v 1
or a
quadrant II vector shorter than ~v 2
Proof: Let S be an element that does not fall on a lattice point. Consider the unit cell of the lattice
containing S (figure 8) with nodes labeled e 1
Connect S to the four corners of the unit cell to get four triangles. At least one of these triangles
has a right or obtuse angle. Wolog, let the triangle be on points e 1
and S. Then both the vector
from e 1
to S and the vector from e 2
to S is shorter than the vector from e 1
to e 2
. Since at least
one of the two is a quadrant I vector, we have a quadrant I vector shorter than ~v 1: 2
Our first main result is the following Theorem. It establishes that if an array has basis vectors in
both quadrants, then in a certain block of the array, which depends on the coefficients of the basis
vectors, all symmetry vectors are linear combinations of the basis vectors. We state the Theorem
in terms of quadrant I for simplicity. Since the array can be rotated so that any quadrant becomes
quadrant I , it applies to all quadrants.
Theorem 1 Let A be an array with basis vectors (r
in quadrants I and II
respectively with c 1
m. Let L be an infinite lattice with the same basis
vectors and containing the element A[0; 0]. Then, in the block
an element is a quadrant I source iff it is a lattice element.
Proof: By Lemma 3, if is a lattice element, then it is a source. Suppose that S is not a
lattice element, but that it is a quadrant I source. We will show that S can not occur within block
By way of contradiction, assume S does occur in prefix block
There is a quadrant I vector ~v associated with S that is not a linear combination of ~v 1
and ~v 2
By Observation 1, copies of A can be aligned with the points of lattice L and the copies will be
in register and cover the plane. Let A i.e. the suffix block originating at
element Because S is a source, ~v maps . For each copy of
A, remove all but A 0 . The copies of A 0 are in register. Since A 0 has dimensions at least r 1
, it is at least as large as a unit cell of the lattice and therefore, the copies of A 0 also cover
the plane. Now every element of the plane is mapped by ~v from an identical element, and there is
a complete copy of A at S. S falls within some cell of lattice L. By Lemma 4, there is a quadrant
I or quadrant II vector ~v 3
from S to some corner e of the cell (or from e to S) which is shorter
than the corresponding basis vector of L. Since there are complete copies of A at S and e, ~v 3
is a
symmetry vector and therefore ~v 1
and ~v 2
are not both basis vectors of A as assumed. 2
Since our quadrants are of size d me \Theta d me, they are no greater in size than the smallest block that
can contain only lattice point sources. The region that contains only lattice point sources can be
larger than the block described in Theorem 1, see [GP-92].
Next, we prove the following important trait about radiant periodic arrays that facilitates their
handling in matching applications [AB-92b, ABF-94b, KR-94]. Origins (A[0; 0]) of complete copies
of a radiant periodic array A that overlap without mismatch can be ordered monotonically.
Definition 5 A set of elements of an array B can be ordered monotonically if the elements can
be ordered so that they have column index nondecreasing and row index nondecreasing (ordered
monotonically in quadrant I) or row index nonincreasing (ordered monotonically in quadrant II).
Our theorem is stated in terms of quadrant I , but generalizes to quadrant II .
Theorem 2 Let A be a radiant periodic array with periodic vector in quadrant I . Let S 1
be quadrant I sources occuring within quadrant I . On each source, place one copy of A by aligning
A[0; 0] with the source. If every pair of copies is in register, then the sources can be ordered
monotonically in quadrant I .
Proof: Suppose two sources A[c 1
cannot be ordered monotonically. That is, c 1
but
. If there is no mismatch in the copies of A at these sources, then by the fact that
) is a periodic, quadrant II symmetry vector and
by definition, A is lattice periodic, a contradiction. 2
As stated earlier, our classification scheme applies to any rectangular array. The major modification
is a new definition of length.
Definition 6 The length of a symmetry vector of a rectangular array is the maximum of the
absolute values of its coefficients scaled to the dimensions of the array. Let A be n rows by m
columns with m - n. Let c) be a symmetry vector in A. Then the length of ~v scaled to the
dimensions of the array is max(r
4 Periodicity and Witness Algorithms
In this section, we present two algorithms, one serial and one parallel for finding all sources in an
array A. In addition, for each location in A which is not a source, our algorithms find a witness
that proves that the overlapping copies of A are not in register.
We want to fill out an array For each location A[i; j] that is a
quadrant I source,
some mismatch. Specifically A[r; c] 9). For each location A[i; j] that is a
quadrant II source,
where
mismatch
i+r

Figure

9:
The witness tables gives the location of a mismatch
(if one exists) for two overlapping patterns:
4.1 The Serial Algorithm
Our serial algorithm (Algorithm makes use of two algorithms (Algorithms 1 and 2) from [ML-84]
which are themselves variations of the KMP algorithm [KMP-77] for string matching. Algorithm 1
takes as input a pattern string w of length m and builds a table lppattern[0::m \Gamma 1] where lppattern[i]
is the length of the longest prefix of w starting at w i . Algorithm 2 takes as input a text string t of
length n and the table produced by Algorithm 1 and produces a table lptext[0::n \Gamma 1] where lptext[i]
is the length of the longest prefix of w starting at t i .
The idea behind Algorithm A is the following: We convert the two-dimensional problem into a
problem on strings (figure 10). Let the array A be processed column by column and suppose we
are processing column j. Assume we can convert the suffix block A[0::m \Gamma string
represents the suffix of row i starting in column j. This will serve as the
text string. Assume also that we can convert the prefix block A[0::m \Gamma string
represents the prefix of row i of length m \Gamma j. This will serve as the
pattern string. Now, use Algorithm 1 to produce the table lppattern for W j and Algorithm 2 to
produce the table lptext for T j . If a copy of the pattern starting at t i matches in every row to t
then is a source. If the pattern doesn't match and the first pattern row
to mismatch is row j] is not a source. The mismatch occurs
between the prefix of pattern row k and the suffix of text row need merely locate the
mismatch to obtain the witness.
In order to treat the suffix and prefix of a row as a single character, we will build a suffix tree for
the array. A suffix tree is a compacted trie of suffixes of a string Each node
v has associated with it the indices [a,b] of some substring of S. If u is the Least
Common Ancestor (LCA) of two nodes v and w, then S(u) is the longest common prefix of S(v)
and S(w) [LV-85]. A tree can be preprocessed in linear time to answer LCA queries in constant
m-j columns

Figure

10:
Representing a block of the array by a string.
is the text and W
is the pattern.
time [HT-84]. Thus, we can answer questions about the length of S(u) in constant time.
Algorithm A Serial algorithm for building a witness array and deciding periodicity class.
Step A.1: Build a suffix tree by concatenating the rows of the array. Preprocess the suffix tree
for least common ancestor queries in order to answer questions about the length of the common
prefix of any two suffixes.
Step A.2: For each column j, fill out
Step A.2.1: Use Algorithm 1 to construct the table lppattern for
w i is the prefix of row i of length j. We can answer questions about the equality
of two characters by consulting the suffix tree. If the common prefix of the two characters
has length at least m \Gamma j then the characters are equal.
Step A.2.2: Use Algorithm 2 to construct the table lptext for
is the suffix of row i starting in column j (also of length Again we test for equality
by reference to the suffix tree.
Step A.2.3: For each row i, if then we have found a quadrant I source
and otherwise, using the suffix tree, compare the suffix of text row
starting in column j with the prefix of pattern row lptext[i]. The length l of the
common prefix will be less than
Step A.3: Repeat step 2 for by building the automata and
processing the columns from the bottom up.
Step A.4: Select quadrant I and quadrant II basis vectors from Witness if they exist.
Step A.5: Use the basis vectors to decide to which of four periodicity classes the pattern belongs.
Theorem 3 Algorithm A is correct and runs in time O(m 2 log j\Sigmaj).
Proof: The correctness of Algorithm A follows from the correctness of Algorithms 1 and 2 [ML-84].
The suffix tree construction [W-73] takes time O(m 2 log j\Sigmaj) while the preprocessing for least common
ancestor queries [HT-84] can be done in time linear in the size of the tree. Queries to the suffix
tree are processed in constant time. The tables lppattern and lptext can be constructed in time
O(m) [ML-84]. For each of m columns, we construct two tables so the total time for steps 2 and 3 is
O(m 2 ). Step 4 can be done in one scan through the witness array and step 5 requires comparing all
vectors to the basis vectors in order to distinguish between the radiant and line periodic classes, so
the time for steps 4 and 5 is O(m 2 ). The total complexity of the pattern preprocessing is therefore
Recently, [GP-92] gave a linear time serial algorithm for the witness computation.
4.2 The Parallel Algorithm
Our parallel algorithm (Algorithm B) makes use of the parallel string matching algorithm (Algo-
rithm 3) from [V-85]. Algorithm 3 takes as input a pattern string w of length m and a text string t
of length n and produces a boolean table true if a complete
copy of the pattern starts at t i . Algorithm 3 first preprocesses the pattern and then processes the
text.
First, for a text of length m, we show how to modify Algorithm 3 to compute match[0::m \Gamma 1],
is a prefix of the pattern. For simplicity, we assume m is a
power of 2. Let

Figure

is a prefix of t i
is a suffix of w 0
For example,
is the prefix of w of length mand S 1
is a suffix of t of the same length. The
following observation embodies the key idea (figure 11):
is a prefix of w of length between m and m, then P 1
is a prefix of
is a suffix of w Similarly, if is a prefix of w of length
between mand m, then the prefix and suffix are P 2
, etc.
Now, for each k - 1, we attempt to match P k in S k\Gamma1 and S k in P k\Gamma1 . If a matched prefix begins
at t i and a matched suffix ends at is a prefix of w.
Using Algorithm 3, we first preprocess the P k and S k as patterns and then use these to process
the appropriate segments as text. We can additionally modify Algorithm 3 so that at every index
where a prefix or suffix does not match, we obtain the location of a mismatch. Since the sum of
the lengths of the P i and S i are no more than a linear multiple of the length of w, the modification
does not increase the complexity of the algorithm and therefore the time complexity of the modified
Algorithm 3 is O(log m) using O( m
log m ) CRCW processors, the same as the unmodified algorithm
[V-85]. In our parallel algorithm, only steps 2 differs from the serial algorithm.
Algorithm B Parallel algorithm for finding sources and building a witness array
Step B.2: For each column j, fill out
Step B.2.1: For each
Step B.2.1.1: Use W j to form P k and P k\Gamma1 and T j to form S k and S k\Gamma1 . Use modified
Algorithm 3 to match P k in S k\Gamma1 and S k in P k\Gamma1 . As in the serial algorithm, use the
suffix tree to answer questions about equality.
Step B.2.1.2: For each row i for
beginning
at t i and S k matches ending at using
the row r of mismatch from modified Algorithm 3, refer to the suffix tree to find the
column c of mismatch and set
Theorem 4 Algorithm B is correct and runs in time O(log m) using O(m 2 ) CRCW processors.
Proof: The suffix tree construction [AILSV-87] and preprocessing for LCA queries [SV-88] is done
in time O(log m) using O(m 2 ) CRCW processors. Step 2 is done in time O(log m) using O( m 2
log
CRCW processors [V-85]. Finding the basis vectors is done by prefix minimum [LF-80] in time
O(log m) using O( m 2
log m ) processors. Distinguishing the line and radiant periodic cases can be done
in constant time using O(m 2 ) processors. The total complexity is therefore O(log m) time using
processors.



--R

"Two-Dimensional Periodicity and its Application"
"Efficient Two-Dimensional Compressed Matching"
"Optimal Parallel Two Dimensional Text Searching on a CREW PRAM,"
"An Alphabet Independent Approach to Two-Dimensional Matching"
"Optimal Two Dimensional Compressed Match- ing,"
"Efficient String Matching"
"Efficient 2-dimensional Approximate Matching of Non-rectangular Figures"
"Fast Parallel and Serial Multidimensional Approximate Array Matching"
"Efficient Pattern Matching with Scaling"
"Parallel Construction of a Suffix Tree with Applications"
"A Technique For Extending Rapid Exact-Match String Matching to Arrays of More Than One Dimension"
"Two Dimensional Pattern Matching"
"A Fast String Searching Algorithm"
"Optimally fast parallel algorithms for preprocessing and pattern matching inone and two dimensions,"
"Note on two dimensional string matching by optimal parallel algorithms,"
"Optimal Parallel Algorithms for String Matching"
"Truly Alphabet Independent Two-Dimensional Pattern Match- ing,"
"Fast Algorithms for Finding Nearest Common Ancestors"
"Alphabet Independent Optimal Parallel Search for 3-Dimensional Patterns,"
"Fast Pattern Matching in Strings"
"Efficient Two Dimensional Pattern Matching in the Presence of
"Parallel Prefix Computation"
"Efficient string matching in the presence of errors"
"An O(n log n) Algorithm for Finding all Repetitions in a String"
"A Unifying Look at d-Dimensional Periodicities and Space Coverings,"
"On Finding Lowest Common Ancestors: Simplification and Parallelization"
"Optimal Parallel Pattern Matching in Strings"
"Deterministic new technique for fast pattern matching"
"Linear Pattern Matching Algorithms"
--TR

--CTR
Richard Cole , Zvi Galil , Ramesh Hariharan , S. Muthukrishnan , Kunsoo Park, Parallel two dimensional witness computation, Information and Computation, v.188 n.1, p.20-67, 10 January 2004
Amihood Amir , Gad M. Landau , Dina Sokol, Inplace 2D matching in compressed images, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Amihood Amir , Gad M. Landau , Dina Sokol, Inplace 2D matching in compressed images, Journal of Algorithms, v.49 n.2, p.240-261, November
Chiara Epifanio , Filippo Mignosi, A multidimensional critical factorization theorem, Theoretical Computer Science, v.346 n.2, p.265-280, 28 November 2005
Filippo Mignosi , Antonio Restivo , Pedro V. Silva, On Fine and Wilf's theorem for bidimensional words, Theoretical Computer Science, v.292 n.1, p.245-262, January
Amihood Amir , Gad M. Landau , Dina Sokol, Inplace run-length 2d compressed search, Theoretical Computer Science, v.290 n.3, p.1361-1383, 3 January
Chiara Epifanio , Michel Koskas , Filippo Mignosi, On a conjecture on bidimensional words, Theoretical Computer Science, v.299 n.1-3, p.123-150,
string matching;witness;parallel algorithm;periodicity;sequential algorithm;two-dimensional