Abstract
This paper presents a real-time randomized streaming string matching algorithm that uses O(logm) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurrences of the pattern, but never misses an actual occurrence.
Work partially supported by the European Research Council (ERC) project SFEROT and by the Israeli Science Foundation grants 35/05 and 347/09.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ergun, F., Jowhari, H., Salgan, M.: Periodicity in Streams (2010) (manuscript)
Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16, 109–114 (1965)
Galil, Z.: String Matching in Real Time. J. Assoc. Comput. Mach. 28(1), 134–149 (1981)
Galil, Z.: Optimal parallel algorithms for string matching. Inform. and Control 67, 144–157 (1985)
Galil, Z., Seiferas, J.: Time-space-optimal string matching. J. Comput. System Sci. 26, 280–294 (1983)
Karp, R.M., Rabin, M.O.: Efficient randomized pattern matching algorithms. IBM J. Res. Develop. 31(2), 249–260 (1987)
Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6, 322–350 (1977)
Porat, B., Porat, E.: Exact And Approxiamate Pattern Matching In The Streaming Model. In: Proc. 50th IEEE Symp. on Foundations of Computer Science, pp. 315–323 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Breslauer, D., Galil, Z. (2011). Real-Time Streaming String-Matching. In: Giancarlo, R., Manzini, G. (eds) Combinatorial Pattern Matching. CPM 2011. Lecture Notes in Computer Science, vol 6661. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21458-5_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-21458-5_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21457-8
Online ISBN: 978-3-642-21458-5
eBook Packages: Computer ScienceComputer Science (R0)
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.