@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. , and , An alphabet-independent approach to two-dimensional pattern-matching, SIAM J. Comput., 1994, 23 (2), pp. 313-323. | MR 1267212 | Zbl 0804.68056
2. , 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. , Optimal parallel detection of squares in strings, Algorithmica, 1992, 8, pp. 285-319. | MR 1186900 | Zbl 0748.68022
4. and , 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. , and , 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. , and , Parallel detection of all palindromes in a string, Theoret. Comput. Sci., 1995, 141 (1), pp. 163-173. | MR 1323153 | Zbl 0873.68039
7. and , Optimal off-line detection of repetitions in a string, Theoret Comput Sci., 1983, 22, pp. 297-315. | MR 693062 | Zbl 0497.68052
8. , , and , On economic construction of the transitive closure of a directed graph, Soviet Math. Dokl., 1970, 11, pp. 1209-1210. | Zbl 0214.23601
9. , Evaluation of general arithmetic expressions, J. Assoc. Comput. Mach., 1974, 21, pp. 201-206. | MR 660280 | Zbl 0276.68010
10. , , and , Transforming comparison model lower bounds to the parallel-random-access-machine, 5th Italian Conference on Theoretical Computer Science, Villa Rufolo, 1995, Italy.
11. and , 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. and , A lower bound for parallel string matching, SIAM J. Comput., 1992, 21 (5), pp. 856-862. | MR 1181403 | Zbl 0756.68048
13. and , Finding all periods and initial palindromes of a string in parallel, Algorithmica, to appear. | MR 1343321 | Zbl 0833.68053
14. , , , , , , and , 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. , 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. , Transducers and repetitions, Theoret. Comput. Sci., 1986, 12, pp. 63-86. | MR 865967 | Zbl 0615.68053
17. , , , and , Constant-time randomized parallel string matching, Manuscript, 1994.
18. , , , and , A constant time optimal parallel algorithm for two dimensional pattern matching. Manuscript, 1993.
19. and , Efficient parallel algorithms to test square-freeness and factorize strings, Inform. Process. Lett., 1991, 38, pp. 57-60. | MR 1113337 | Zbl 0736.68033
20. and , 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. , and , Relations between concurrent-write models of parallel computation, SIAM J. Comput., 1988, 17 (3), pp. 606-627. | MR 941948 | Zbl 0652.68065
22. and , 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. , 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. , Optimal parallel algorithms for string matching, Inform. and Control, 1985, 67, pp. 144-157. | MR 833865 | Zbl 0588.68022
25. , A constant-time optimal parallel string-matching algorithm. In Proc. 24th ACM Symp. on Theory of Computing, 1992, pp. 69-76.
26. and , 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. and , Faster parallel string matching via larger deterministic samples. J. Algorithms, 1994, 16 (2), pp. 295-308. | MR 1258241 | Zbl 0797.68083
28. , and , Fast pattern matching in strings, SIAM J. Comput. Sci., 1977, 6, pp. 322-350. | MR 451916 | Zbl 0372.68005
29. , 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. and , Parallel prefix computation, J. Assoc. Comput. Mach., 1980, 27 (4), pp. 831-838. | MR 594702 | Zbl 0445.68066
31. and , The equation am = bn cp in a free group. Michigan Math. J., 1962, 9, pp. 289-298. | MR 162838 | Zbl 0106.02204
32. and , 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. and , 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. , 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. , 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. , 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. , Über unendliche zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl. (Cristiania), 1906, 7, pp. 1-22. | JFM 39.0283.01
38. , Ü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. , Optimal parallel pattern matching in strings, Inform. and Control, 1985, 67, pp. 91-113. | MR 833862 | Zbl 0588.68023
40. , Deterministic sampling - a new technique for fast pattern matching, SIAM J. Comput., 1990, 20 (1), pp. 22-40. | MR 1082134 | Zbl 0716.68074