Linear-time string-matching using only a fixed number of local storage locations
作者： Zvi Galil , Joel Seiferas
DOI: 10.1016/S0304-3975(81)80006-0
关键词:
摘要: Abstract We report a linear-time string-matching algorithm for random-access machine without dynamic storage allocation. To do this, we tell how to adapt cited fill its needs by temporarily borrowing some of the space occupied input pattern. In automata-theoretic terms, run on writing multihead finite automaton with restricted alphabet.
elsevier.com
sci-hub.se 参考文章(6)
M. S. Paterson, M. J. Fischer, STRING-MATCHING AND OTHER PRODUCTS Massachusetts Institute of Technology. ,(1974)
Donald E Knuth, James H Morris, Jr, Vaughan R Pratt, Fast Pattern Matching in Strings SIAM Journal on Computing. ,vol. 6, pp. 323- 350 ,(1977) , 10.1137/0206024
Zvi Galil, Joel Seiferas, Saving Space in Fast String-Matching SIAM Journal on Computing. ,vol. 9, pp. 417- 438 ,(1980) , 10.1137/0209032
Michael J. Fischer, Arnold L. Rosenberg, Real-time solutions of the origin-crossing problem Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 2, pp. 257- 263 ,(1968) , 10.1007/BF01694010
Benton L. Leong, Joel I. Seiferas, New Real-Time Simulations of Multihead Tape Units Journal of the ACM. ,vol. 28, pp. 166- 180 ,(1981) , 10.1145/322234.322246
Benton Leong, Joel Seiferas, New real-time simulations of multihead tape units symposium on the theory of computing. pp. 239- 248 ,(1977) , 10.1145/800105.803414