A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String

Full text

Pdf (404 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 3 (July 1975) table of contents

Pages: 346 - 351

Year of Publication: 1975

ISSN:0004-5411

Author

Glenn Manacher

Computer Center and Department of Information Engineering, University of Illinois, Chicago, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 43, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321892.321896 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AHo, A. Currents in the Theory of Computing. Prentice-Hall, Englewood Cliffs, N. J., 1973.
	2	COOK, S.A. Linear time simulation of deterministic two-way pushdown automata. Information Processing 71, North~Holland Pub. Co., Amsterdam, 1972, pp. 75-80.
	3	M. J. Fischer , M. S. Paterson, STRING-MATCHING AND OTHER PRODUCTS, Massachusetts Institute of Technology, Cambridge, MA, 1974
	4	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	5	KNUTH, D. E., MORRm, J. H., ANB PRX~r, V.R. Fast pattern matching in strings. Tech. Rep. CS 440, Computer Sci. Dep., Stanford U., Stanford, Calif., 1974.
	6	SI.ISENEO, A.O. Recognition of palindromes by multihead Turing machines. Proc. of the Steklov Math. Inst., Aead. of Sciences of the USSR, Vol. 129, 1973, pp. 30--202.
	7	WEISER, P. Linear pattern matching algorithms. IEEE Symp. on Switching and Automata Theory, Vol. 14, 1973, pp. 1-11.

CITED BY 5

	Zvi Galil , Joel Seiferas, A Linear-Time On-Line Recognition Algorithm for ``Palstar'', Journal of the ACM (JACM), v.25 n.1, p.102-111, Jan. 1978
	Zvi Galil, Real-time algorithms for string-matching and palindrome recognition, Proceedings of the eighth annual ACM symposium on Theory of computing, p.161-173, May 03-05, 1976, Hershey, Pennsylvania, United States
	Zvi Galil, String Matching in Real Time, Journal of the ACM (JACM), v.28 n.1, p.134-149, Jan. 1981
	Alberto Apostolico , Maxime Crochemore, String pattern matching for a deluge survival kit, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Zvi Galil, On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognition, ACM SIGACT News, v.7 n.4, p.26-30, November-Decmeber 1975