Fast Pattern Matching in Strings

Donald E. Knuth, James H. Morris Jr., Vaughan R. Pratt, 1977, SIAM Journal on Computing

About this paperEnglish日本語beside Englishbeside 日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

SO KHỚP MẪU NHANH TRONG CHUỖI*

DONALD E. KNUTH†, JAMES H. MORRIS, JR.‡ VÀ VAUGHAN R. PRATT¶

Tóm tắt. Một thuật toán được trình bày để tìm tất cả các lần xuất hiện của một chuỗi đã cho bên trong một chuỗi khác, với thời gian chạy tỷ lệ với tổng độ dài của các chuỗi. Hằng số tỷ lệ đủ nhỏ để làm cho thuật toán này có tính ứng dụng thực tế, và thủ tục này cũng có thể được mở rộng để xử lý một số bài toán so khớp mẫu tổng quát hơn. Một ứng dụng lý thuyết của thuật toán cho thấy rằng tập các phép nối của các palindrome chẵn, tức là ngôn ngữ {ααR}∗\{\alpha\alpha^R\}^*, có thể được nhận biết trong thời gian tuyến tính. Các thuật toán khác có thời gian chạy trung bình còn nhanh hơn cũng được xem xét.

Từ khóa. mẫu, chuỗi, soạn thảo văn bản, so khớp mẫu, bộ nhớ trie, tìm kiếm, chu kỳ của một chuỗi, palindrome, thuật toán tối ưu, chuỗi Fibonacci, biểu thức chính quy

Các chương trình soạn thảo văn bản thường cần tìm kiếm trong một chuỗi ký tự để tìm các thể hiện của một chuỗi “mẫu” đã cho; chúng ta muốn tìm tất cả các vị trí, hoặc có thể chỉ vị trí ngoài cùng bên trái, tại đó mẫu xuất hiện như một chuỗi con liên tục của văn bản. Ví dụ, catenaryc a t e n a r y chứa mẫu tent e n, nhưng chúng ta không xem canaryc a n a r y là một chuỗi con.

Cách hiển nhiên để tìm kiếm một mẫu khớp là thử tìm kiếm tại mọi vị trí bắt đầu của văn bản, từ bỏ việc tìm kiếm ngay khi một ký tự không đúng được tìm thấy.

References

  1. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974.
  2. Alfred V. Aho and Margaret J. Corasick, Efficient string matching: An aid to bibliographic search, Comm. ACM, 18 (1975), pp. 333–340.
  3. M. Beeler, R. W. GOSPER AND R. SCHROEPPEL, HAKMEM, Memo No. 239, M.I.T. Artificial Intelligence Laboratory, Cambridge, Mass., 1972.
  4. Robert S. Boyer and J. Strother Moore, A fast string searching algorithm, manuscript dated December 29, 1975; Stanford Research Institute, Menlo Park, Calif., and Xerox Palo Alto Research Center, Palo Alto, Calif.
  5. S. A. Cook, Linear time simulation of deterministic two-way pushdown automata, Information Processing 71, North-Holland, Amsterdam, 1972, pp. 75–80.
  6. Pascal DiethelM and Peter Roizen, An efficient linear search for a pattern in a string, unpublished manuscript dated April, 1972; World Health Organization, Geneva, Switzerland.
  7. N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc., 16 (1965), pp. 109–114.
  8. Michael J. Fischer and Michael S. Paterson, String matching and other products, SIAM-AMS Proc., vol. 7, American Mathematical Society, Providence, R.I., 1974, pp. 113–125.
  9. Zvi Galil, On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognition, SIGACT News, 7 (1975), No. 4, pp. 26–30.
  10. E. N. Gilbert, Synchronization of binary messages, IRE Trans. Information Theory, IT-6 (1960), pp. 470–477.
  11. Sheila A. Greibach, The hardest context-free language, this Journal, 2 (1973), pp. 304–310.
  12. Malcolm C. Harrison, Implementation of the substring test by hashing, Comm. ACM, 14 (1971), pp. 777–779.
  13. Richard M. Karp, Raymond E. Miller and Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees, and arrays, ACM Symposium on Theory of Computing, vol. 4, Association for Computing Machinery, New York, 1972, pp. 125–136.
  14. Donald E. Knuth, Fundamental Algorithms, The Art of Computer Programming, Vol. 1, Addison-Wesley, Reading, Mass., 1968; 2nd edition 1973.
  15. ———, Sequences with precisely k + 1 k-blocks, Solution to problem E2307, Amer. Math. Monthly, 79 (1972), pp. 773–774.
  16. ———, On the translation of languages from left to right, Information and Control, 8 (1965), pp. 607–639.
  17. ———, Structured programming with go to statements, Computing Surveys, 6 (1974), pp. 261–301.
  18. Donald E. Knuth, James H. Morris, Jr. and Vaughan R. Pratt, Fast pattern matching in strings, Tech. Rep. CS440, Computer Science Department, Stanford Univ., Stanford, Calif., 1974.
  19. R. C. Lyndon and M. P. Schützenberger, The equation $a^M = b^N c^P$ in a free group, Michigan Math. J., 9 (1962), pp. 289–298.
  20. Glenn Manacher, A new linear-time on-line algorithm for finding the smallest initial palindrome of a string, J. Assoc. Comput. Mach., 22 (1975), pp. 346–351.
  21. A. Markoff, Sur une question de Jean Bernoulli, Math. Ann., 19 (1882), pp. 27–36.
  22. J. H. Morris, Jr. and Vaughan R. Pratt, A linear pattern-matching algorithm, Tech. Rep. 40, Univ. of California, Berkeley, 1970.
  23. A. O. Slisenko, Recognition of palindromes by multihead Turing machines, Dokl. Steklov Math. Inst., Akad. Nauk SSSR, 129 (1973), pp. 30–202. (In Russian.)
  24. Ken Thompson, Regular expression search algorithm, Comm. ACM, 11 (1968), pp. 419–422.
  25. B. A. Venkov, Elementary Number Theory, Wolters-Noordhoff, Groningen, the Netherlands, 1970.
  26. Peter Weiner, Linear pattern matching algorithms, IEEE Symposium on Switching and Automata Theory, vol. 14, IEEE, New York, 1973, pp. 1–11.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.