zbMATH — the first resource for mathematics

Parallel detection of all palindromes in a string. (English) Zbl 0873.68039
Summary: This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string: 1. An \(O(\log n)\) time, \(n\)-processor algorithm over general alphabets. In the 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.

68P10 Searching and sorting
Full Text: DOI
[1] Apostolico, A.; Breslauer, D.; Galil, Z., Optimal parallel algorithms for periods, palindromes and squares, (), 296-307
[2] Arlazarov, V.L.; Dinie, E.A.; Kronrod, M.A.; Faradzev, I.A., On economic construction of the transitive closure of a directed graph, Soviet math. dokl., 11, 1209-1210, (1970) · Zbl 0214.23601
[3] Brent, R.P., Evaluation of general arithmetic expressions, J. assoc. comput. Mach., 21, 201-206, (1974) · Zbl 0276.68010
[4] Breslauer, D.; Galil, Z., An optimal O(loglogn) time parallel string matching algorithm, SIAM J. comput., 19, 1051-1058, (1990) · Zbl 0711.68057
[5] D. Breslauer and Z. Galil, Finding all periods and initial palindromes of a string in parallel, Algorithmica, to appear. · Zbl 0833.68053
[6] Cook, S.A., Linear time simulation of deterministic two-way pushdown automata, (), 75-80
[7] Crochemore, M.; Rytter, W., Usefulness of the karp-Miller-rosenberg algorithm in parallel computations on strings and arrays, Theoret. comput. sci., 88, 59-82, (1991) · Zbl 0737.68037
[8] Fich, F.E.; Ragde, R.L.; Wigderson, A., Relations between concurrent-write models of parallel computation, (), 179-189
[9] Fischer, M.J.; Paterson, M.S., String matching and other products, (), 113-125
[10] Galil, Z., Two fast simulations which imply some fast string matching and palindrome-recognition algorithms, Inform. process. lett., 4, 85-87, (1976) · Zbl 0328.68047
[11] Galil, Z., Palindrome recognition in real time by a multitape Turing machine, J. comput. system sci., 16, 140-157, (1978) · Zbl 0386.03020
[12] Galil, Z., Optimal parallel algorithms for string matching, Inform. and control, 67, 144-157, (1985) · Zbl 0588.68022
[13] Galil, Z.; Seiferas, J., A linear-time on-line recognition algorithm for “palstar”, J. assoc. comput. Mach., 25, 102-111, (1978) · Zbl 0365.68058
[14] Kedem, Z.; Landau, G.M.; Palem, K., Optimal parallel suffix-prefix matching algorithm and applications, (), 388-398
[15] Knuth, D.E.; Morris, J.H.; Pratt, V.R., Fast pattern matching in strings, SIAM J. comput., 6, 322-350, (1977) · Zbl 0372.68005
[16] Lyndon, R.C.; Schutzenberger, M.P., The equation am = bncp in a free group, Michigan math. J., 9, 289-298, (1962) · Zbl 0106.02204
[17] Manacher, G., A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string, J. assoc. comput. Mach., 22, 346-351, (1975) · Zbl 0305.68027
[18] English translation by R.H. Silverman (Amer. Math. Soc., Providence, RI, 1976) 25 208. · Zbl 0326.02027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.