Journal of the ACM Bibliography
Maxime Crochemore and Dominique Perrin. Two-way
string-matching. Journal of the ACM, 38(3):651-675, July
1991.
[BibTeX entry]
Categories and Subject Descriptors:
D.1.0 [Programming Techniques]; F.2.2 [Analysis
of Algorithms and Problem Complexity]: Nonnumerical Algorithms
and Problems; G.2.2 [Discrete Mathematics]: Graph
Theory; I.5 [Pattern Recognition]; I.7 [Text
Processing]
General Terms:
Algorithms, Design, Theory
Additional Key Words and Phrases:
Analysis of Algorithms, combinatorial algorithms, pattern matching, text
processing
Selected papers that cite this one
- A. Apostolico and M. Crochemore. Fast parallel Lyndon
factorization with applications. Mathematical Systems
Theory, 28(2):89-108, March/April 1995.
- Dany Breslauer. Saving comparisons in
the Crochemore-Perrin string-matching algorithm. Theoretical
Computer Science, 158(1-2):177-192, 20 May 1996.
- Dany Breslauer, Livio Colussi, and Laura Toniolo. On the comparison
complexity of the string prefix-matching problem. Journal of
Algorithms, 29(1):18-67, October 1998.
- Dany Breslauer and Zvi Galil. Efficient
comparison based string matching. Journal of
Complexity, 9(3):339-365, September 1993.
- Dany Breslauer, Tao Jiang, and Zhigen Jiang. Rotations of
periodic strings and short superstrings. Journal of
Algorithms, 24(2):340-353, August 1997.
- Livio Colussi and Laura Toniolo. How the character
comparison order shapes the shift function of on-line pattern matching
algorithms. Theoretical Computer Science,
163(1-2):117-144, 30 August 1996.
- S. Muthukrishnan and K. Palem. Non-standard
stringology: Algorithms and complexity. In Proceedings of the
Twenty-Sixth Annual ACM Symposium on the Theory of Computing,
pages 770-779, Montréal, Québec, Canada, 23-25 May 1994.
Selected references
- Zvi Galil. String matching
in real time. Journal of the ACM, 28(1):134-149,
January 1981.
- Richard M. Karp, Raymond E. Miller, and Arnold L. Rosenberg. Rapid identification of
repeated patterns in strings, trees and arrays. In Conference
Record, Fourth Annual ACM Symposium on Theory of Computing, pages
125-136, Denver, Colorado, 1-3 May 1972.
- Edward M. McCreight. A
space-economical suffix tree construction algorithm. Journal
of the ACM, 23(2):262-272, April 1976.
- Peter Weiner. Linear
pattern matching algorithms. In 14th Annual Symposium on
Switching and Automata Theory, pages 1-11, The University of
Iowa, 15-17 October 1973. IEEE.
Shortcuts: