Efficient string matching on packed texts
Breslauer, D. ; Gasieniec, Leszek
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996), p. 521-544 / Harvested from Numdam
Publié le : 1996-01-01
@article{ITA_1996__30_6_521_0,
     author = {Breslauer, D. and Gasieniec, Leszek},
     title = {Efficient string matching on packed texts},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {30},
     year = {1996},
     pages = {521-544},
     mrnumber = {1454828},
     zbl = {0877.68047},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1996__30_6_521_0}
}
Breslauer, D.; Gasieniec, Leszek. Efficient string matching on packed texts. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) pp. 521-544. http://gdmltest.u-ga.fr/item/ITA_1996__30_6_521_0/

1. C. Amir, G. Benson and M. Farach, An alphabet-independent approach to two-dimensional pattern-matching, SIAM J. Comput., 1994, 23 (2), pp. 313-323. | MR 1267212 | Zbl 0804.68056

2. A. Apostolico, On context constrained squares and repetitions in a string, RAIRO Informatique théorique, 1984, 18 (2), pp. 147-159. | Numdam | MR 761514 | Zbl 0543.68067

3. A. Apostolico, Optimal parallel detection of squares in strings, Algorithmica, 1992, 8, pp. 285-319. | MR 1186900 | Zbl 0748.68022

4. A. Apostolico and D. Breslauer, An optimal O (log log n) time parallel algorithm for detecting all squares in a string, SIAM J. Comput., to appear. | MR 1417902 | Zbl 0864.68045

5. A. Apostolico, D. Breslauer and Z. Galil, Optimal parallel algorithms for periods, palindromes and squares. In Proc. 19th International Colloquium on Automata, Languages, and Programming, number 623 in Lecture Notes in Computer Science, pages 206-307. Springer-Verlag, Berlin, Germany, 1992.

6. A. Apostolico, D. Breslauer and Z. Galil, Parallel detection of all palindromes in a string, Theoret. Comput. Sci., 1995, 141 (1), pp. 163-173. | MR 1323153 | Zbl 0873.68039

7. A. Apostolico and F. P. Preparata, Optimal off-line detection of repetitions in a string, Theoret Comput Sci., 1983, 22, pp. 297-315. | MR 693062 | Zbl 0497.68052

8. V. L. Arlazarov, E. A. Dinic, M. A. Kronrod and I. A. Faradzev, On economic construction of the transitive closure of a directed graph, Soviet Math. Dokl., 1970, 11, pp. 1209-1210. | Zbl 0214.23601

9. R. P. Brent, Evaluation of general arithmetic expressions, J. Assoc. Comput. Mach., 1974, 21, pp. 201-206. | MR 660280 | Zbl 0276.68010

10. D. Breslauer, A. Czumaj, D. Dubhasi and F. Meyer Auf Der Heide, Transforming comparison model lower bounds to the parallel-random-access-machine, 5th Italian Conference on Theoretical Computer Science, Villa Rufolo, 1995, Italy.

11. D. Breslauer and Z. Galil, An optimal O (log log n) time parallel string matching algorithm, SIAM J. Comput., 1990, 19 (6), pp. 1051-1058. | MR 1069098 | Zbl 0711.68057

12. D. Breslauer and Z. Galil, A lower bound for parallel string matching, SIAM J. Comput., 1992, 21 (5), pp. 856-862. | MR 1181403 | Zbl 0756.68048

13. D. Breslauer and Z. Galil, Finding all periods and initial palindromes of a string in parallel, Algorithmica, to appear. | MR 1343321 | Zbl 0833.68053

14. R. Cole, M. Crochemore, Z. Galil, L. Gasieniec, R. Hariharan, S. Muthukrishnan, K. Park and W. Rytter, Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. In Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 248-258. | MR 1328425

15. M. Crochemore, An optimal algorithm for Computing the repetitions in a word, Inform. Process. Lett., 1981, 12 (5), pp. 244-250. | MR 632873 | Zbl 0467.68075

16. M. Crochemore, Transducers and repetitions, Theoret. Comput. Sci., 1986, 12, pp. 63-86. | MR 865967 | Zbl 0615.68053

17. M. Crochemore, Z. Galil, L. Gasieniec, K. Park and W. Rytter, Constant-time randomized parallel string matching, Manuscript, 1994.

18. M. Crochemore, L. Gasieniec, R. Hariharan, S. Muthukrishnan and W. Rytter, A constant time optimal parallel algorithm for two dimensional pattern matching. Manuscript, 1993.

19. M. Crochemore and W. Rytter, Efficient parallel algorithms to test square-freeness and factorize strings, Inform. Process. Lett., 1991, 38, pp. 57-60. | MR 1113337 | Zbl 0736.68033

20. M. Crochemore and W. Rytter, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Theoret. Comput. Sci., 1991, 88, pp. 59-82. | MR 1130372 | Zbl 0737.68037

21. F. E. Rich, R. L. Ragde and A. Wigderson, Relations between concurrent-write models of parallel computation, SIAM J. Comput., 1988, 17 (3), pp. 606-627. | MR 941948 | Zbl 0652.68065

22. M. J. Fischer and M. S. Paterson, String matching and other products. In R. M. KARP, editor, Complexity of Computation, pp. 113-125. American Mathematical Society, Prividence, RI., 1974. | MR 400782 | Zbl 0301.68027

23. Z. Galil, Palindrome recognition in real time by a multiple turing machine, J. Comput. System. Sci., 1978, 16 (2), pp. 140-157. | MR 483670 | Zbl 0386.03020

24. Z. Galil, Optimal parallel algorithms for string matching, Inform. and Control, 1985, 67, pp. 144-157. | MR 833865 | Zbl 0588.68022

25. Z. Galil, A constant-time optimal parallel string-matching algorithm. In Proc. 24th ACM Symp. on Theory of Computing, 1992, pp. 69-76.

26. Z. Galil and K. Park, Truly alphabet-independent two-dimensional pattern matching. In Proc. 33th IEEE Symp. on Foundations of Computer Sciences, 1992, pp. 247-256. | Zbl 0942.68707

27. T. Goldberg and U. Zwick, Faster parallel string matching via larger deterministic samples. J. Algorithms, 1994, 16 (2), pp. 295-308. | MR 1258241 | Zbl 0797.68083

28. D. E. Knuth, J. H. Morris and V. R. Pratt, Fast pattern matching in strings, SIAM J. Comput. Sci., 1977, 6, pp. 322-350. | MR 451916 | Zbl 0372.68005

29. S. R. Kosaraju, Computation of squares in a string. In Proc. 5th Symp. on Combinatorial Pattern Matching, number 807 in Lecture Notes in Computer Science, pp. 146-150. Springer-Verlag, Berlin, Germany, 1994.

30. R. E. Ladner and M. J. Fischer, Parallel prefix computation, J. Assoc. Comput. Mach., 1980, 27 (4), pp. 831-838. | MR 594702 | Zbl 0445.68066

31. R. C. Lyndon and M. P. Schützenbrger, The equation am = bn cp in a free group. Michigan Math. J., 1962, 9, pp. 289-298. | MR 162838 | Zbl 0106.02204

32. G. M. Main and R. J. Lorentz, An O (n log n) algorithm for finding all repetitions in a string, J. Algorithms, 1984, 5, pp. 422-432. | MR 756167 | Zbl 0547.68083

33. G. M. Main and R. J. Lorentz, Linear time recognition of squarefree strings. In A. APOSTOLICO and Z. GALIL, editors, Combinatorial Algorithms on Words, volume 12 of NATO ASI Series F, pp. 271-278. Springer-Verlag, Berlin, Germany, 1985. | MR 815345 | Zbl 0572.68068

34. G. Manacher, A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string, J. Assoc. Comput. Mach., 1975, 22, pp. 346-351. | Zbl 0305.68027

35. M. O. Rabin, Discovering repetitions in strings. In A. APOSTOLICO and Z. GALIL, editors, Combinatorial Algorithms on Words, volume 12 of NATO ASI Series F, pp. 279-288. Springer-Verlag, Berlin, Germany, 1985. | MR 815346 | Zbl 0604.68074

36. A. O. Slisenko, Recognition of palindromes by multihead turing machines. In V. P. ORVERKOV and N. A. SONIN, editors, Problems in the Constructive Trend in Mathematics VI (Proceedings of the Steklov Institute of Mathematics, No. 129), pp. 30-202. Academy of Sciences of the USSR, 1973. English Translation by R. H. SILVERMAN, pp. 25-208, Amer. Math. Soc., Providence, RI, 1976. | MR 432422 | Zbl 0326.02027

37. A. Thue, Über unendliche zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl. (Cristiania), 1906, 7, pp. 1-22. | JFM 39.0283.01

38. A. Thue, Über die gegenseitige lage gleicher teile gewisser zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl. (Cristiania), 1912, 1, pp. 1-67. | JFM 44.0462.01

39. U. Vishkin, Optimal parallel pattern matching in strings, Inform. and Control, 1985, 67, pp. 91-113. | MR 833862 | Zbl 0588.68023

40. U. Vishkin, Deterministic sampling - a new technique for fast pattern matching, SIAM J. Comput., 1990, 20 (1), pp. 22-40. | MR 1082134 | Zbl 0716.68074