Multiple Pattern Matching Algorithms on Collage System

1. A.V. Aho and M. Corasick. Efficient string matching: An aid to bibliographic search. Comm. ACM, 18(6):333–340, 1975.

   Article  MathSciNet  MATH  Google Scholar 

2. A. Amir and G. Benson. Efficient two-dimensional compressed matching. In Proc. Data Compression Conference, page 279, 1992.

   Google Scholar 

3. M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New York, 1994.

   MATH  Google Scholar 

4. A.S. Fraenkel and J. Simpson. How many squares can a string contain? J. Combin. Theory Ser. A, 82:112–120, 1998.

   Article  MathSciNet  MATH  Google Scholar 

5. L.C.K. Hui. Color set size problem with application to string matching. In Combinatorial Pattern Matching, volume 644 of Lecture Notes in Computer Science, pages 230–243. Springer-Verlag, 1992.

   Chapter  Google Scholar 

6. J. Kärkkäinen, G. Navarro, and E. Ukkonen. Approximate string matching over Ziv-Lempel compressed text. In Proc. 11th Ann. Symp. on Combinatorial Pattern Matching, volume 1848 of Lecture Notes in Computer Science, pages 195–209. Springer-Verlag, 2000.

   Chapter  Google Scholar 

7. T. Kida, Y. Shibata, M. Takeda, A. Shinohara, and S. Arikawa. A unifying framework for compressed pattern matching. In Proc. 6th International Symp. on String Processing and Information Retrieval, pages 89–96. IEEE Computer Society, 1999.

   Google Scholar 

8. T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa. Multiple pattern matching in LZW compressed text. Journal of Discrete Algorithms. to appear (previous version in DCC’98 and CPM’99).

   Google Scholar 

9. T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa. Multiple pattern matching in LZW compressed text. In J.A. Storer and M. Cohn, editors, Proc. Data Compression Conference’ 98, pages 103–112. IEEE Computer Society, 1998.

   Google Scholar 

10. D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comput, 6(2):323–350, 1977.

    Article  MathSciNet  MATH  Google Scholar 

11. N.J. Larsson and A. Moffat. Offline dictionary-based compression. In Proc. Data Compression Conference’ 99, pages 296–305. IEEE Computer Society, 1999.

    Google Scholar 

12. T. Matsumoto, T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Bit-parallel approach to approximate string matching in compressed texts. In Proc. 7th International Symp. on String Processing and Information Retrieval, pages 221–228. IEEE Computer Society, 2000.

    Google Scholar 

13. G. Navarro, T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Faster approximate string matching over compressed text. In Proc. Data Compression Conference 2001. IEEE Computer Society, 2001. to appear.

    Google Scholar 

14. G. Navarro and M. Raffinot. A general practical approach to pattern matching over Ziv-Lempel compressed text. In Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, volume 1645 of Lecture Notes in Computer Science, pages 14–36. Springer-Verlag, 1999.

    Chapter  Google Scholar 

15. G. Navarro and J. Tarhio. Boyer-Moore string matching over Ziv-Lempel compressed text. In Proc. 11th Ann. Symp. on Combinatorial Pattern Matching, volume 1848 of Lecture Notes in Computer Science, pages 166–180.Springer-Verlag, 2000.

    Chapter  Google Scholar 

16. C.G. Nevill-Manning, I.H. Witten, and D.L. Maulsby. Compression by induction of hierarchical grammars. In Proc. Data Compression Conference’ 94, pages 244–253. IEEE Press, 1994.

    Google Scholar 

17. W. Ruzzo. Tree-size bounded alternation. Journal of Computer and System Sciences, 21(2):218–235, 1980.

    Article  MathSciNet  MATH  Google Scholar 

18. W. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22(3):365–383, 1981.

    Article  MathSciNet  MATH  Google Scholar 

19. W. Rytter. Algorithms on compressed strings and arrays. In Proc. 26th Ann. Conf. on Current Trends in Theory and Practice of Infomatics. Springer-Verlag, 1999.

    Google Scholar 

20. Y. Shibata, T. Kida, S. Fukamachi, M. Takeda, A. Shinohara, T. Shinohara, and S. Arikawa. Speeding up pattern matching by text compression. In Proc. 4th Italian Conference on Algorithms and Complexity, volume 1767 of Lecture Notes in Computer Science, pages 306–315. Springer-Verlag, 2000.

    Chapter  Google Scholar 

21. Y. Shibata, T. Matsumoto, M. Takeda, A. Shinohara, and S. Arikawa. A Boyer-Moore type algorithm for compressed pattern matching. In Proc. 11th Ann. Symp. on Combinatorial Pattern Matching, volume 1848 of Lecture Notes in Computer Science, pages 181–194. Springer-Verlag, 2000.

    Chapter  Google Scholar 

22. I. Sudborough. On the tape complexity of deterministic context-free languages. Journal of ACM, 25:405–414, 1978.

    Article  MathSciNet  MATH  Google Scholar 

23. M. Takeda, Y. Shibata, T. Matsumoto, T. Kida, A. Shinohara, S. Fukamachi, T. Shinohara, and S. Arikawa. Speeding up string pattern matching by text compression: The dawn of a new era. Transactions of Information Processing Society of Japan, 2001. to appear.

    Google Scholar 

Download references