Efficient string matching on packed texts
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 6, pp. 521-544. 
@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},
     pages = {521--544},
     publisher = {EDP-Sciences},
     volume = {30},
     number = {6},
     year = {1996},
     mrnumber = {1454828},
     zbl = {0877.68047},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1996__30_6_521_0/}
}
TY  - JOUR
AU  - Breslauer, D.
AU  - Gasieniec, Leszek
TI  - Efficient string matching on packed texts
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1996
SP  - 521
EP  - 544
VL  - 30
IS  - 6
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1996__30_6_521_0/
LA  - en
ID  - ITA_1996__30_6_521_0
ER  - 
%0 Journal Article
%A Breslauer, D.
%A Gasieniec, Leszek
%T Efficient string matching on packed texts
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1996
%P 521-544
%V 30
%N 6
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1996__30_6_521_0/
%G en
%F 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) no. 6, pp. 521-544. http://archive.numdam.org/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 | Zbl

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

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

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 | Zbl

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 | Zbl

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 | Zbl

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

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

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 | Zbl

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

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

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

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

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

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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

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

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

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

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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

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 | Zbl

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 | Zbl

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

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

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

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