Fast Pattern Matching in Strings

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

About this paperEnglishTiếng Việtbeside Englishbeside Tiếng Việt

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.

高速文字列パターン照合*

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

要約。ある文字列内に別の与えられた文字列が出現するすべての位置を、その文字列の長さの和に比例する実行時間で発見するアルゴリズムを提示する。比例定数は、このアルゴリズムを実用に供するのに十分小さく、またこの手続きは、より一般的ないくつかのパターン照合問題を扱うよう拡張することもできる。このアルゴリズムの理論的応用により、偶数回文の連結の集合、すなわち言語{ααR}∗\{\alpha\alpha^R\}^*が線形時間で認識可能であることを示す。平均的にはさらに高速に実行される他のアルゴリズムについても考察する。

キーワード。パターン、文字列、テキスト編集、パターン照合、トライメモリ、探索、文字列の周期、回文、最適アルゴリズム、フィボナッチ文字列、正規表現

テキスト編集プログラムでは、与えられた「パターン」文字列の出現を探すために、しばしば文字列を検索する必要がある。我々は、パターンがテキストの連続した部分文字列として現れるすべての位置、あるいは左端の位置だけを発見したい。例えば、catenaryc a t e n a r yはパターンtent e nを含むが、canaryc a n a r 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 日本語 by gpt-5, against glossary version 6. Translated from the English.