String and Pattern Matching Bibliography (6/27/2000)

Prepared by:

Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, New York 11451-0001

Email: (for additions, suggestions, and corrections)

Aho, A., Algorithms for finding patterns in Strings, in Handbook of Theoretical Computer Science, J. van Leeuwen (ed.), Volume A, MIT Press, Cambridge, 1994.

Aho, A and J. Corasick, Efficient string matching: an aid to bibliographic search, Comm. ACM 18 (1975) 333-340.

Apostolico, A., General pattern matching, in Algorithms and Theory of Computation Handbook, M. Atallah (ed.), CRC Press, Boca Raton, 1999.

Boyer, R. and J. Moore, A fast string searching algorithm, Comm. ACM 20 (1977) 762-772.

Cole, R., Tight bounds on the complexity of the Boyer-Moore pattern matching algorithm SIAM J. Computing 23 (1994) 1075-1091.

Crochemore, M. and C. Hancart, Pattern matching in strings, in Algorithms and Theory of Computation Handbook, M. Atallah (ed.), CRC Press, Boca Raton, 1999.

Crochemore, M. and W. Rytter, Text Algorithms, Oxford U. Press, New York, 1994.

Farach-Colton, M., (ed.), Combinatorial Pattern Matching, Lecture Notes in Computer Science, Volume 1448, Springer-Verlag, New York, 1998.

Galil, Z., String matching in real time, J. ACM 28 (1981) 134-149.

Galil, Z. and R. Giancarlo, Data structures and algorithms for approximate string matching, Journal of Complexity 4 (1988) 33-72.

Gusfield, D., Algorithms on Strings, Trees, and Sequences, Cambridge U. Press, Cambridge, 1997.

Karp, R. and M. Rabin, Efficient randomized pattern-matching algorithms, IBM J. Res. Dev. 31 (1987) 249-260.

Knuth, D. and J. Morris, V. Pratt, Fast pattern matching in strings, SIAM J. Computing 6 (1977) 323-350.

Sankoff, D. and J. Kruskal, (eds.), Time Warps, Sting Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addisson-Wesley, Reading, 1983.

Stephen, G., String Searching Algorithms, World Scientific Press, Singapore, 1994.

Back to list of bibliographies