Efficient string matching on packed texts

D. Breslauer; Leszek Gasieniec

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)

  • Volume: 30, Issue: 6, page 521-544
  • ISSN: 0988-3754

How to cite

top

Breslauer, D., and Gasieniec, Leszek. "Efficient string matching on packed texts." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.6 (1996): 521-544. <http://eudml.org/doc/92550>.

@article{Breslauer1996,
author = {Breslauer, D., Gasieniec, Leszek},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {string-matching algorithm},
language = {eng},
number = {6},
pages = {521-544},
publisher = {EDP-Sciences},
title = {Efficient string matching on packed texts},
url = {http://eudml.org/doc/92550},
volume = {30},
year = {1996},
}

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
PB - EDP-Sciences
VL - 30
IS - 6
SP - 521
EP - 544
LA - eng
KW - string-matching algorithm
UR - http://eudml.org/doc/92550
ER -

References

top
  1. 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. Zbl0804.68056MR1267212
  2. 2. A. APOSTOLICO, On context constrained squares and repetitions in a string, RAIRO Informatique théorique, 1984, 18 (2), pp. 147-159. Zbl0543.68067MR761514
  3. 3. A. APOSTOLICO, Optimal parallel detection of squares in strings, Algorithmica, 1992, 8, pp. 285-319. Zbl0748.68022MR1186900
  4. 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. Zbl0864.68045MR1417902
  5. 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. 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. Zbl0873.68039MR1323153
  7. 7. A. APOSTOLICO and F. P. PREPARATA, Optimal off-line detection of repetitions in a string, Theoret Comput Sci., 1983, 22, pp. 297-315. Zbl0497.68052MR693062
  8. 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. Zbl0214.23601
  9. 9. R. P. BRENT, Evaluation of general arithmetic expressions, J. Assoc. Comput. Mach., 1974, 21, pp. 201-206. Zbl0276.68010MR660280
  10. 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. 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. Zbl0711.68057MR1069098
  12. 12. D. BRESLAUER and Z. GALIL, A lower bound for parallel string matching, SIAM J. Comput., 1992, 21 (5), pp. 856-862. Zbl0756.68048MR1181403
  13. 13. D. BRESLAUER and Z. GALIL, Finding all periods and initial palindromes of a string in parallel, Algorithmica, to appear. Zbl0833.68053MR1343321
  14. 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. MR1328425
  15. 15. M. CROCHEMORE, An optimal algorithm for Computing the repetitions in a word, Inform. Process. Lett., 1981, 12 (5), pp. 244-250. Zbl0467.68075MR632873
  16. 16. M. CROCHEMORE, Transducers and repetitions, Theoret. Comput. Sci., 1986, 12, pp. 63-86. Zbl0615.68053MR865967
  17. 17. M. CROCHEMORE, Z. GALIL, L. GASIENIEC, K. PARK and W. RYTTER, Constant-time randomized parallel string matching, Manuscript, 1994. Zbl0885.68078
  18. 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. Zbl0912.68067
  19. 19. M. CROCHEMORE and W. RYTTER, Efficient parallel algorithms to test square-freeness and factorize strings, Inform. Process. Lett., 1991, 38, pp. 57-60. Zbl0736.68033MR1113337
  20. 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. Zbl0737.68037MR1130372
  21. 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. Zbl0652.68065MR941948
  22. 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. Zbl0301.68027MR400782
  23. 23. Z. GALIL, Palindrome recognition in real time by a multiple turing machine, J. Comput. System. Sci., 1978, 16 (2), pp. 140-157. Zbl0386.03020MR483670
  24. 24. Z. GALIL, Optimal parallel algorithms for string matching, Inform. and Control, 1985, 67, pp. 144-157. Zbl0588.68022MR833865
  25. 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. 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. Zbl0942.68707
  27. 27. T. GOLDBERG and U. ZWICK, Faster parallel string matching via larger deterministic samples. J. Algorithms, 1994, 16 (2), pp. 295-308. Zbl0797.68083MR1258241
  28. 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. Zbl0372.68005MR451916
  29. 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. 30. R. E. LADNER and M. J. FISCHER, Parallel prefix computation, J. Assoc. Comput. Mach., 1980, 27 (4), pp. 831-838. Zbl0445.68066MR594702
  31. 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. Zbl0106.02204MR162838
  32. 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. Zbl0547.68083MR756167
  33. 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. Zbl0572.68068MR815345
  34. 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. Zbl0305.68027
  35. 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. Zbl0604.68074MR815346
  36. 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. Zbl0326.02027MR432422
  37. 37. A. THUE, Über unendliche zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl. (Cristiania), 1906, 7, pp. 1-22. JFM39.0283.01
  38. 38. A. THUE, Über die gegenseitige lage gleicher teile gewisser zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl. (Cristiania), 1912, 1, pp. 1-67. Zbl44.0462.01JFM44.0462.01
  39. 39. U. VISHKIN, Optimal parallel pattern matching in strings, Inform. and Control, 1985, 67, pp. 91-113. Zbl0588.68023MR833862
  40. 40. U. VISHKIN, Deterministic sampling - a new technique for fast pattern matching, SIAM J. Comput., 1990, 20 (1), pp. 22-40. Zbl0716.68074MR1082134

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.