@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. An alphabet-independent approach to two-dimensional pattern-matching, SIAM J. Comput., 1994, 23 (2), pp. 313-323. | MR 1267212 | Zbl 0804.68056
, and ,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. 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
and ,5. 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.
, and ,6. Parallel detection of all palindromes in a string, Theoret. Comput. Sci., 1995, 141 (1), pp. 163-173. | MR 1323153 | Zbl 0873.68039
, and ,7. Optimal off-line detection of repetitions in a string, Theoret Comput Sci., 1983, 22, pp. 297-315. | MR 693062 | Zbl 0497.68052
and ,8. On economic construction of the transitive closure of a directed graph, Soviet Math. Dokl., 1970, 11, pp. 1209-1210. | Zbl 0214.23601
, , and ,9. Evaluation of general arithmetic expressions, J. Assoc. Comput. Mach., 1974, 21, pp. 201-206. | MR 660280 | Zbl 0276.68010
,10. Transforming comparison model lower bounds to the parallel-random-access-machine, 5th Italian Conference on Theoretical Computer Science, Villa Rufolo, 1995, Italy.
, , and ,11. 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
and ,12. A lower bound for parallel string matching, SIAM J. Comput., 1992, 21 (5), pp. 856-862. | MR 1181403 | Zbl 0756.68048
and ,13. Finding all periods and initial palindromes of a string in parallel, Algorithmica, to appear. | MR 1343321 | Zbl 0833.68053
and ,14. 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
, , , , , , and ,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. Constant-time randomized parallel string matching, Manuscript, 1994.
, , , and ,18. A constant time optimal parallel algorithm for two dimensional pattern matching. Manuscript, 1993.
, , , and ,19. Efficient parallel algorithms to test square-freeness and factorize strings, Inform. Process. Lett., 1991, 38, pp. 57-60. | MR 1113337 | Zbl 0736.68033
and ,20. 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
and ,21. Relations between concurrent-write models of parallel computation, SIAM J. Comput., 1988, 17 (3), pp. 606-627. | MR 941948 | Zbl 0652.68065
, and ,22. 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
and ,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. Truly alphabet-independent two-dimensional pattern matching. In Proc. 33th IEEE Symp. on Foundations of Computer Sciences, 1992, pp. 247-256. | Zbl 0942.68707
and ,27. Faster parallel string matching via larger deterministic samples. J. Algorithms, 1994, 16 (2), pp. 295-308. | MR 1258241 | Zbl 0797.68083
and ,28. Fast pattern matching in strings, SIAM J. Comput. Sci., 1977, 6, pp. 322-350. | MR 451916 | Zbl 0372.68005
, and ,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. Parallel prefix computation, J. Assoc. Comput. Mach., 1980, 27 (4), pp. 831-838. | MR 594702 | Zbl 0445.68066
and ,31. The equation am = bn cp in a free group. Michigan Math. J., 1962, 9, pp. 289-298. | MR 162838 | Zbl 0106.02204
and ,32. 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
and ,33. 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
and ,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
,