Maxime Crochemore
- 1 AHO, A. V. Pattern matching in strings. In R. V. Book, ed., Formal Language Theory: Perspectives and Open Problems. Academic Press, Orlando, Fla., 1980, pp. 325-347.Google Scholar
- 2 Avio, A. V., AND CORASICK, M.J. Efficient string matching: An aid to bibliographic search. Commun. ACM 18, 6 (June 1975), 333-340. Google Scholar
- 3 APOSTOLICO, A,, AND GIANCARLO, R. The Boyer-Moore-Galil searching strategies revisited. SlAM J. Comput. 15, 1 (1986), 98-105. Google Scholar
- 4 BEAN, D. R., EHr~ENFEUCrW, A., AND MCNULTY, G. F. Avoidable patterns in strings of symbols. Pacific J. Math. 85 (1979), 261-294.Google Scholar
- 5 BZlaSTEL, J. Transductions and Context-Free Languages. Teubner, Stuttgart, Germany, 1979Google Scholar
- 6 BLUMER. A., BLUMER, J., EHRENFEUCHT, A., HAUSSLER, D., CHEN, M. T., AND SEIFERAS, J. The smallest automaton recogmzing the subwords of a text. Theoret. Comput. Sci. 40, 1 (1985), 31-56.Google Scholar
- 7 BOOTH, K.S. Lex~cographically least circular substrings. Inf. Process. Lett. 10, 4/5 (1980), 240-242.Google Scholar
- 8 BOYER, R. S., AND MOORE, J. S. A fast string searching algorithm, Commun. ACM 20, 10 (Oct. 1977), 762-772. Google Scholar
- 9 CESARI, Y., AND VINCENT, M. Une caractdrisation des roots p~riodiques. C.R. Acad. Sci. 286, s~rie A (1978), 1175.Google Scholar
- 10 CROCHEMORE, M. Transducers and repetitions Theoret. Comput. Sci. 45 (1986), 63-86. Google Scholar
- 11 CROCHEMORE, M. Longest common factor of two words. In H. Ehrig, R. Kowalska, G. Levi, and U. Montanari, eds., TAPSOFT'87, vol 1. Springer-Verlag, 1987, pp. 26-36. Google Scholar
- 12 CROCHEMORE, M. String-matching and periods. Bull. Euro. Assoc. Theor. Comput. Sci. 39 (1989), 149-153.Google Scholar
- 13 DUVAL, J. P. Mots de Lyndon et p~riodicit~. R.A.I.R.O. Informat. Theor. 14, 2 (1980), 181-191.Google Scholar
- 14 DUVAL, J.P. Factorizing words over an ordered alphabet. J. Algorithms 4 (1983), 363-381.Google Scholar
- 15 GALIL, Z. On improving the worst case running time of the Boyer-Moore string-matching algorithm. Commun. ACM 22, 9 (Sept. 1979), 505-508. Google Scholar
- 16 GALIL, Z. String matching in real time. J. ACM 28, 1 (Jan. 1981), 134-149. Google Scholar
- 17 GALIL, Z., AND SEIFERAS, J. Time space optimal string matching. J. Comput. Syst. Sci. 26 (1983), 280-294.Google Scholar
- 18 GUIBAS, L. J., AND ODLYZKO, A.M. A new proof of the linearity of the Boyer-Moore string searching algorithm. SIAM j. Comput. 9, 4 (1980), 672-682.Google Scholar
- 19 HORSPOOL, N. Practical fast searching in strings. Softw. Prac. Exp. 10 (1980), 501-506.Google Scholar
- 20 KARl:', R. M., MILLER, R. E., AND ROSENBERG, A.L. Rapid identification of repeated patterns in strings, trees, and arrays. In Proceedings of the 4th Annual A CM Symposium on Theory of Computing (Denver, Colo., May 1-3). ACM, New York, 1972, pp. 125-136. Google Scholar
- 21 KNUTtt, D. E., MORRIS, J. H., AND PRATT, V.R. Fast pattern matching in strings, SIAM J. Comput. 6, 2 (1977), 323-350.Google Scholar
- 22 LOTHAIRE, M. Combinatorics on Words. Addison-Wesley, Reading, Mass., 1982.Google Scholar
- 23 LANDAU, G. M., AND VISHKIN, U. Efficient string matching with k mismatches. Theor. Comput. Sci. 43 (1986), 239-249. Google Scholar
- 24 MCCREIGHT, E. M. A space-economical suffix tree construction algorithm. J. A CM 23, 2 (Apr. 1976), 262-272. Google Scholar
- 25 RarEST, R.L. On the worst-case behavior of string-searching algorithms. SIAM J. Comput. 6, 4 (1977), 669-674.Google Scholar
- 26 ROZENBERG, G., AND SALOMAA, A. The Mathematical Theory of L Systems, Academic Press, New York, 1980. Google Scholar
- 27 RYTTER, W. A correct preprocessing algorithm for Boyer-Moore string-searching. SIAM j. Comput. 9, 3 (1980), 509-512.Google Scholar
- 28 SEDGEWICK, R. Algorithms. Addison-Wesley, Reading, Mass., 2d ed., 1988. Google Scholar
- 29 SHILOACH, V. Fast canonization of circular strings. J. Algorithms 2 (1981), 107-121.Google Scholar
- 30 SLISENKO, A.O. Detection of periodicities and string-matching in real-time. J. Soy. Math. 22, 3 (1983), 1316-1387.Google Scholar
- 31 THOMPSON, K. Regular expression search algorithm. Commun. ACM 11, 6 (June 1968), 419-422. Google Scholar
- 32 UKKONEN, E. Finding approximate patterns in strings, J. Algorithms 6 (1985), 132-137.Google Scholar
- 33 VISHKIN, U. Optimal parallel pattern matching in strings. Inf. Cont. 67 (1985), 91-113. Google Scholar
- 34 WEINER, P. Linear pattern matching algorithms. In Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory. IEEE, New York, 1972, pp. 1-11.Google Scholar
Index Terms
- Two-way string-matching
Recommendations
An algorithm to improve the performance of string matching
Approximate string matching algorithms are techniques used to find a pattern 'P' in a text 'T' partially or exactly. These techniques become very important in terms of performance and the accuracy of searching results. In this paper, we propose a ...
String Matching with Wildcards in the Massively Parallel Computation Model
SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and ArchitecturesWe study distributed algorithms for string matching problem in presence of wildcard characters. Given a string T (a text), we look for all occurrences of another string P (a pattern) as a substring of string T. Each wildcard character in the pattern ...
A Composite Boyer-Moore Algorithm for the String Matching Problem
PDCAT '10: Proceedings of the 2010 International Conference on Parallel and Distributed Computing, Applications and TechnologiesThe string matching problem has found wide application in computer science, molecular biology, genetic engineering, semantics and many other fields. In this paper, we give analysis to several classical algorithms, KMP, BM and their improvements. Then, ...
Reviews
Violet R. Syrotiuk
The simple string-matching algorithm presented here uses the critical factorization theorem. First, the pattern x is factored into x=x l x r by a critical position l (shown to reduce to the computation of the maximal suffix of x ) and the period of the pattern is computed. The string-matching algorithm itself has two phases. The first phase of the algorithm compares x r with the text, scanning from left to right. If a mismatch is found in this phase, then the pattern is shifted right by l . If no mismatch occurs, then the second phase of the algorithm compares x l with the text, scanning from right to left. If a mismatch occurs, then the pattern is shifted by the period of the pattern. This two-way string-matching algorithm uses linear time and constant space, which compares with the well-known Knuth-Morris-Pratt and Boyer-Moore algorithms. The paper is well written. The algorithms are described simply, and proofs of termination and correctness are accompanied by many diagrams that help illustrate both how the algorithm works and what the variables in the algorithm represent.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments