Zvi Galil
- 1 AHO, A.V., HOPCROET, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
- 2 BAKER, T.P. An extended pattern matching algorithm applied to rectangular arrays. Unpublished manuscript, Computer Science Department, Cornell University, Ithaca, New York, August 1972.Google Scholar
- 3 FISCHER, P.C., MEYER, A.R., AND ROSENBERG, A.L. Real-time simulation ofmultihead tape units. ~ ACM 19, 4 (Oct. 1972), 590-607. Google Scholar
- 4 FISCHER, M.J., AND PATERSON, i .S . String-matching and other products. Siam AMS Proe. on Complexity of Computation, R.M. Karp, Ed., American Mathematical Society, Providence, R.I., 1974, pp. 113-126.Google Scholar
- 5 FREIDSON, R.1. A characterization of the complexity of recursive predicates. Proc. Steklov Inst. Math 113 (1970), 91-117.Google Scholar
- 6 GALIL, Z. Real-time algorithms for string matching and palindrome recognition. Proc. 8th Ann. ACM Symp. on Theory of Computing, Hershey, Pa., May 1976, 161-173. Google Scholar
- 7 GALIL, Z. Palindrome recognition in real time. by multitape Turing machines. ~ Comput. Syst. Sci. 16, 2 (1978), 140-157.Google Scholar
- 8 HARTMANIS, J., AND STEARNS, R.E. On the computation complexity of algorithms. Trans. Amer. Math. Soc. 117 (1965), 285-306.Google Scholar
- 9 KNUTH, D.E., MORRIS, J.H., AND PRATT, V.R. Fast pattern matching in strings. SlAM J. Comput. 6, 2 (1977), 323-350.Google Scholar
- 10 MANACHER, G. A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string.I. ACM 22, 3 (July 1975), 346-351. Google Scholar
- 11 MAT1JESEVIC, YU. V. Real-time recognition of the inclusion relation. ~ Soviet Math. 1, 1 (1973), 64- 70.Google Scholar
- 12 MORRIS, J.H. JR., AND PRATT, V.R. A linear pattern matching algorithm. Tech. Rep. No. 40, Computing Center, University of California, Berkeley, Calif. June 1970.Google Scholar
- 13 RABIN, M.O. Real-time computation. Israel J. Math. 1 (1963), 203-211.Google Scholar
- 14 SLISENKO, A.O. Private communication, October 1976.Google Scholar
- 15 TARJAN, R.E., AND YAO, A.C.-C. Storing a sparse table. Commun. ACM 22, II (Nov. 1979), 606- 611. Google Scholar
Index Terms
- String Matching in Real Time
Recommendations
String Matching under a General Matching Relation
In standard string matching, each symbol matches only itself, In other string matching problems, e.g., the string matching with "don t-cares" problem, a symbol may match several symbols. In general, an arbitrary many-to-many matching relation might hold ...
Average-optimal string matching
The exact string matching problem is to find the occurrences of a pattern of length m from a text of length n symbols. We develop a novel and unorthodox filtering technique for this problem. Our method is based on transforming the problem into multiple ...
Approximate string matching in sublinear expected time
SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer ScienceThe k differences approximate string matching problem specifies a text string of length n, a pattern string of length m, and the number k of differences (insertions, deletions, substitutions) allowed in a match, and asks for every location in the text ...
Comments