«Parallel Detection of all Palindromes in a String Alberto Apostolico Dany Breslauery Zvi Galilz Abstract This paper presents two e cient ...»
Parallel Detection of all Palindromes in a
Alberto Apostolico Dany Breslauery Zvi Galilz
This paper presents two e cient concurrent-read concurrent-write parallel algorithms that nd all palindromes in a given string:
1. An O(log n) time, n-processor algorithm over general alphabets. In
case of constant size alphabets the algorithm requires only n= log n
processors, and thus achieves an optimal-speedup.
2. An O(log log n) time, n log n= log log n-processor algorithm over general alphabets. This is the fastest possible time with the number of processors used.
These new results improve on the known parallel palindrome detection algorithms by using smaller auxiliary space and either by making fewer operations or by achieving a faster running time.
1 Introduction Palindromes are symmetric strings that read the same forward and backward.
Palindromes have been studied for centuries as word puzzles and more recently have found several important uses in formal languages and computability theory.
Formally, a non-empty string w is a palindrome if w = wR, where wR denotes the string w reversed. It is convenient to distinguish between even length Computer Science Department, Purdue University, West Lafayette, IN 47907, and Dipartimento di Elettronica e Informatica, Universita di Padova, 35131 Padova, Italy. Partially supported by NSF Grants CCR-89-00305 and CCR-92-01078, by NATO Grant CRG 900293 and by the National Research Council of Italy.
y Istituto di Elaborazione della Informazione, Consiglio Nazionale delle Ricerche, Via S. Maria 46, 56126 Pisa, Italy. Partially supported by the European Research Consortium for Informatics and Mathematics postdoctoral fellowship. Part of this work was done while visiting at the Institut National de Recherche en Informatique et en Automatique, Rocquencourt, France.
z Computer Science Department, Columbia University, New York, NY 10027, and Computer Science Department, Tel-Aviv University, Ramat-Aviv 69978, Israel. Partially supported by NSF Grants CCR-90-14605 and CISE Institutional Infrastructure Grant CDA-90-24735.
palindromes that are strings of the form vvR and odd length palindromes that are strings of the form vavR, where a is a single alphabet symbol.
Given a string S 1::n], we say that there is an even palindrome of radius R centered at position k of S 1::n], if S k ? i] = S k + i ? 1] for i = 1; ; R. We ^ say that there is an odd palindrome of radius R centered on position k of S 1::n], ^ ^ if S k ? i] = S k + i] for i = 1; ; R. The radius R (or R) is maximal if there 1 R + 1 centered at the same position. In this paper we is no palindrome of radius ^ are interested in computing the maximal radii R k] and R k] of the even and the odd palindromes which are centered at all positions k of S 1::n].
Manacher 17] discovered an elegant linear-time on-line sequential algorithm that nds all initial palindromes in a string. Galil 11] and Slisenko 18] presented real-time initial palindrome recognition algorithms for multi-tape Turing machines.
It is interesting to note that the existence of e cient algorithms that nd initial palindromes in a string was also implied by theoretical results on fast simulation 6, 10]. Knuth, Morris and Pratt 15] gave another linear-time algorithm that nds all initial palindromes in a string.
A closer look at Manacher's algorithm shows that it not only nds the initial palindromes, but it also computes the maximal radii of palindromes centered at all positions of the input string. Thus Manacher's algorithm solves the problem considered in this paper in linear time.
A parallel algorithm is said to be optimal, or to achieve an optimal-speedup, if its time-processor product, which is the total number of operation performed, is equal to the running time of the fastest sequential algorithm. Note that there exists a trivial constant-time CRCW-PRAM algorithm that nds all palindromes in a string using O(n2) processors. However, the large number of processors leaves much to be desired.
Fischer and Paterson 9] noticed that any string matching algorithm that nds all overhanging occurrences of a string in another can also nd all initial palindromes. This observation has been used by Apostolico, Breslauer and Galil 1] to construct an optimal O(log log n) time parallel algorithm that nds all initial palindromes in strings over general alphabets, improving an O(log n) time nonoptimal algorithm of Galil 12]. Breslauer and Galil 5] show that any parallel algorithm that nds initial palindromes in strings over general alphabets requires (dn=pe + log logd1+p=ne 2p) time using p processors. Thus, the fastest possible optimal parallel algorithm that nds initial palindromes must take (log log n) time and this is the time required even with n log n processors.
Crochemore and Rytter 7] discuss a general framework for solving string problems in parallel. (Similar results have been discovered by Kedem, Landau and Palem 14].) Most problems they consider, including the problem of detecting For the convenience of our notation, we sometimes refer to indices in S 1::n] that are out of the de ned range. It is agreed that all unde ned symbols are distinct and di erent from the symbols in S 1::n].
all palindromes in a string, have O(log n) time, n-processor CRCW-PRAM algorithms. However, their method uses O(n1+ ) space and requires that the input symbols are drawn from an ordered alphabet, an unnecessary restriction in the palindrome detection problem.
This paper presents two new CRCW-PRAM algorithms for detecting all palindromes in a string. Both algorithms have the same time-processor product as the Crochemore-Rytter algorithm, use linear space and work under the general alphabet assumption, where the only access they have to the input symbols is by pairwise comparisons that determine if two symbols are equal.
1. The rst algorithm takes O(log n) time using n processors. If the alphabet size is bounded by a constant, then the number of processors can be reduced to n= log n, making the algorithm optimal.
2. The second algorithm takes O(log log n) time using n log n= log log n processors. This algorithm is the fastest possible with the number of processors used since it takes at least this time to nd the initial palindromes.
The paper is organized as follows. Section 2 overviews some parallel algorithms and tools that are used in the new algorithms. Section 3 gives important properties of periods and palindromes. Sections 4 and 5 describe the new algorithms.
Concluding remarks and open problems are listed in Section 6.
2 The CRCW-PRAM Model The algorithms described in this paper are for the concurrent-read concurrentwrite parallel random access machine model. We use the weakest version of this model called the common CRCW-PRAM. In this model many processors have access to a shared memory. Concurrent read and write operations are allowed at all memory locations. If several processors attempt to write simultaneously to the same memory location, it is assumed that they always write the same value.
Our palindrome detection algorithms use an algorithm of Fich, Ragde and Wigderson 8] to compute the minima of n integers from the range 1; ; n, in constant time using an n-processor CRCW-PRAM. The second algorithm uses Breslauer and Galil's 4] parallel string matching algorithm that takes O(log log n) time using an n= log log n-processor CRCW-PRAM.
One of the major issues in the design of PRAM algorithms is the assignment of processors to their tasks. In this paper, the assignment can be done using standard techniques and the following general theorem.
Theorem 2.1 (Brent 3]) Any synchronous parallel algorithm of time t that consists of a total of x elementary operations can be implemented on p processors in dx=pe + t time.
3 Periods and Palindromes Periods are regularities of strings that are exploited in many e cient string algorithms.
De nition 3.1 A string S has a period u if S is a pre x of uk for some large enough k. The shortest period of a string S is called the period of S. Alternatively, a string S 1::m] has a period of length if S i] = S i + ], for i = 1; ; m ?.
Lemma 3.2 (Lyndon and Schutzenberger 16]) If a string of length m has two periods of lengths p and q and p + q m, then it also has a period of length gcd(p; q).
Throughout the paper, we discuss only the detection of even palindromes. If interested also in the odd palindromes, one can convert the input string S 1::n] ^ into a string S 1::2n] that is obtained by doubling each symbol of the original ^ string. It is not di cult to verify that the string S 1::2n] has even palindromes that correspond to each odd and even palindrome of S 1::n]. Thus, the palindrome ^ detection algorithms can be presented with the string S 1::2n] as their input, while their output is considered in the context of the original string S 1::n]. Note that ^ an odd palindrome in S 1::2n] consists of equal symbols.
The palindrome detection algorithms use the following lemmas that allow them to handle e ciently long palindromes that are centered close to each other. The lemmas concern only even palindromes, but there exist similar versions for odd palindromes.
Lemma 3.3 Assume that the string S 1::n] contains two even palindromes whose radii are at least r centered at positions k and l, such that k l and l ? k r.
Then the substring S k ? r::l + r ? 1] is periodic with period length 2(l ? k).
Proof: If 1 i r, then S k ? i] = S k + i ? 1] = S l ? (l ? k) + i ? 1] = S l + (l ? k) ? i] = S k + 2(l ? k) ? i] and S l + i ? 1] = S l ? i] = S k + (l ? k) ? i] = S k ? (l ? k) + i ? 1] = S l ? 2(l ? k) + i ? 1];
establishing that S k ? r::l + r ? 1] is periodic with period length 2(l ? k). 2
4 An O(log n) time algorithm Theorem 4.1 There exists an algorithm that computes the radii of all even palindromes in a string S 1::n] in O(log n) time using n processors and linear space.
Proof: The algorithm consists of blog nc ? 1 steps. In step number, 0 blog nc ? 2, the input string S 1::n] is partitioned into consecutive blocks of length 2. (Only palindrome centers are partitioned. The palindromes themselves may overlap.) The algorithm proceeds simultaneously in all bn=2 c blocks. It takes constant time and makes O(2 ) operations in each block. Therefore, each step takes constant time using n processors.
The description below concentrates on a single block. The ideal situation is when the radii of all palindromes that are centered in the block are determined by the end of the step. However, this will not always be the case. The algorithm
maintains the following invariant at the completion of step number :
The palindromes whose radii are determined are exactly those whose radii are smaller than 2 +2.
The main observation is that at the beginning of step number, the position of all undetermined radii in the block form an arithmetic progression. Let c1 c2 cl be the positions of palindromes whose radii are not determined. We show that if l 3, then ci+1 ? ci = ci ? ci?1 for i = 2; ; l ? 1. By the invariant and Lemma 3.3, S ci?1 ? 2 +1 ::ci + 2 +1 ] is periodic with period length 2(ci ? ci?1) and S ci ? 2 +1 ::ci+1 + 2 +1] is periodic with period length 2(ci+1 ? ci). Therefore, by Lemma 3.2, S ci ? 2 +1::ci + 2 +1 ] is periodic with period length 2c, where c = gcd(ci ? ci?1; ci+1 ? ci). But by Lemma 3.4, if ci ? ci?1 c, then the radius of the palindrome centered at position ci ?c is larger than the radius of the palindrome centered at position ci?1 or the palindrome centered at position ci, violating the invariant. Therefore, ci ?ci?1 = c and similarly also ci+1 ?ci = c, establishing that the sequence of undetermined radii fcig forms an arithmetic progression.
Note that an arithmetic progression can be represented by three integers: the start, the di erence and the sequence length. If the undetermined radii in the two 2 ?1-blocks that compose the current 2 -block are represented this way, then the two representations are merged using constant number of operations. This permits an e cient access to all palindromes whose radii are undetermined.
We show next how to maintain the invariant at the end of each step. The computation takes constant time and O(2 ) operations using symbol comparisons and the integer minima algorithm.
1. If the block contains a single undetermined radius, then the algorithm checks if the radius is at least 2 +2 or nds the radius exactly if it is shorter.
2. If the block contains a non-trivial arithmetic progression of undetermined radii fcig, i = 1::l, with di erence c, then let S L:: R] be the maximal substring that contains S c1 ?c::cl +c?1] and is periodic with period length 2c. By Lemma 3.4, the radius of the palindrome centered at position ci is exactly min(ci ? L; R ?ci +1) except for at most one of the ci's that satis es ci ? L = R ? ci + 1.
The algorithm checks if S c1 ? 2 +2::cl + 2 +2 ? 1] is periodic with period length 2c. If this substring is not periodic, then the algorithm has found at least one of L and R and it can determine all radii which are smaller than 2 +2 by Lemma 3.4. If the algorithm found both L and R and there is a palindrome with undetermined radius centered at position ( L + R + 1)=2, then the algorithm checks if the radius of this palindrome is at least 2 +2 or nds the radius exactly if it is shorter.
Sometime the algorithm nds radii of longer palindromes but we prefer to leave these radii undetermined to maintain the invariant.
In the beginning of step number 0 there is a single undetermined radius in each block and the invariant is satis ed at the end of the step. At the end of step number blog nc ? 2 all radii have been determined. 2 If the size of the alphabet is bounded by some constant, then the O(log n) time algorithm described above can be implemented using only n= log n processors, similarly to Galil's 12] string matching algorithm. This is achieved using the \four Russians trick" 2] of packing log n symbols into one number, in order to facilitate comparisons of up to log n symbols in a single operation. Note, that over general alphabet the algorithm described above is obsolete since the algorithm given in the next section is more e cient.