Jump to content

Apostolico–Giancarlo algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Mahanga (talk | contribs) at 17:48, 5 December 2008 (notable, part of NIST). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Apostolico-Giancarlo algorithm - an algorithm which remembers the length of the longest suffix of the pattern ending at the right position of the window at the end of each attempt. These information are stored in a table skip. It was designed by Apostolico and Giancarlo.

References

  • APOSTOLICO A., GIANCARLO R., 1986, The Boyer-Moore-Galil string searching strategies revisited, SIAM Journal on Computing 15(1):98-105.
  • CROCHEMORE, M., LECROQ, T., 1997, Tight bounds on the complexity of the Apostolico-Giancarlo algorithm, Information Processing Letters 63(4):195-203.
  • CROCHEMORE, M., RYTTER, W., 1994, Text Algorithms, Oxford University Press.
  • GUSFIELD, D., 1997, Algorithms on strings, trees, and sequences: Computer Science and Computational Biology, Cambridge University Press.
  • LECROQ, T., 1992, Recherches de mot, Ph. D. Thesis, University of Orléans, France.
  • LECROQ, T., 1995, Experimental results on string matching algorithms, Software - Practice & Experience 25(7):727-765.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Apostolico–Giancarlo_algorithm&oldid=256076921"