Abstract
In this paper, we present a distributed algorithm which runs on the N-cube and solves the string matching problem. A basic prefix-suffix matching technique is used as a building block in the construction of the algorithm. As opposed to the parallel algorithm so far designed on shared-memory PRAM models, our algorithm runs distributively on fixed N-cube and especially applies to long texts. Given a text t[1n] and a pattern x[1m] cut into N non-overlapping pieces each of size s≤m, and taking the preprocessing into account, one can find all occurrences of x in t in time O(s+log N) with N processors on a MIMD hypercube.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B.S. Chlebus and L. Gasieniec. Optimal pattern matching on meshes. In 11th Ann. Symp. on Theoretical Aspects of Computer Science, pages 213–224, 1994.
M. Crochemore and D. Perrin. Two way string-matching. Association for Computing Machinery, 38(3):651–675, 1991.
A. Czumaj, Z. Galil, L. Gasieniec, K. Park, and W. Plandowski. Work-time optimal parallel algorithms for strings problems. Manuscript, 1994.
Z. Galil. A constant-time optimal parallel string matching algorithm. In 24th ACM Symp. on Theory of Computing, pages 69–76, 1992.
Z. Galil and J. Seiferas. Time space optimal string matching. J. Comput. Syst. Sci., 26:280–294, 1983.
L. Gasieniec, W. Plandowski, and W. Rytter. Constant-space string matching with smaller number of comparisons: sequential sampling. In 6th Annual Symposium on Combinatorial Pattern Matching, volume 937 of Lecture Note in Computer Science. Springer-Verlag, 1995.
C.T. Ho and S.L. Johnsson. Distributed routing algorithms for broadcasting and personalized communication in hypercubes. In International Conference on Parallel Processing, pages 640–648, 1986.
O.H. Ibarra, T.C. Pong, and S.M. Sohn. String processing on the hypercube. In IEEE Transactions on Acoustics, Speech and Signal Processing, volume 38, pages 160–164, January 1990.
J. Jájá. Introduction to Parallel Algorithms. Addison-Wesley, Reading, Massachusetts, 1992.
Z.M. Kedem, G.M. Landau, and K.V. Palem. Optimal parallel suffix-prefix matching algorithm and applications. In ACM Symposium on Parallel Algorithms and Architectures, pages 388–398, 1989.
D.K. Kim and K. Park. String matching in hypertext. In 6th Annuel Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, pages 318–329, 1995.
U. Vishkin. Deterministic sampling — a new technique for fast pattern matching. SIAM J. Comput, 20:22–40, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Moussouni, F., Lavault, C. (1996). N-cube string matching algorithm with long texts. In: Deza, M., Euler, R., Manoussakis, I. (eds) Combinatorics and Computer Science. CCS 1995. Lecture Notes in Computer Science, vol 1120. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61576-8_93
Download citation
DOI: https://doi.org/10.1007/3-540-61576-8_93
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61576-7
Online ISBN: 978-3-540-70627-4
eBook Packages: Springer Book Archive