Efficient string matching on packed texts

 Access to full text

 Full (PDF)

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