Pattern matching in dynamic texts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pattern matching in dynamic texts

Full text

Pdf (986 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 819 - 828

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

Stephen Alstrup	The IT University in Copenhagen, Glentevej 67, DK-2400 Copenhagen NV, Denmark
Gerth Stølting Brodal	BRICS, Basic Research in Computer Science, Centre of the Danish National Research Foundation and Department of Computer Science, University of Aarhus, Ny Munkegade, DK-8000 Ârhus C, Denmark
Theis Rauhe	The IT University in Copenhagen, Glentevej 67, DK-2400 Copenhagen NV, Denmark

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 34, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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

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	Alberto Apostolico , Zvi Galil, Pattern matching algorithms, Oxford University Press, Oxford, 1997
	2	Paolo Atzeni , Giansalvatore Mecca, Cut and paste, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.144-153, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263678]
	3	Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
	4	Siu-Wing Cheng , Moon-Pun Ng, Isomorphism testing and display of symmetries in dynamic trees, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.202-211, January 28-30, 1996, Atlanta, Georgia, United States
	5	Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
	6	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	7	Paul F. Dietz, Maintaining order in a linked list, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.122-127, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802184]
	8	Paul F. Dietz , Rajeev Raman, Persistence, amortization and randomization, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.78-88, January 28-30, 1991, San Francisco, California, United States
	9	P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
	10	M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and Robert Endre Tarjan. Dynamic perfect hashing: Upper and lower bounds. In Proc. 29th Ann. Syrup. on Foundations of Computer Science (FOGS), pages 524-531, 1988.
	11	P. Ferragina. Dynamic data structures for string matching problems. Ph.D. Thesis:TD-3/97., Department of informatica, University of Pisa.
	12	Paolo Ferragina, Dynamic text indexing under string updates, Journal of Algorithms, v.22 n.2, p.296-328, Feb. 1997 [doi>10.1006/jagm.1996.0814 ]
	13	Paolo Ferragina , Roberto Grossi, Fast incremental text editing, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.531-540, January 22-24, 1995, San Francisco, California, United States
	14	Paolo Ferragina , Roberto Grossi, Optimal On-Line Search and Sublinear Time Update in String Matching, SIAM Journal on Computing, v.27 n.3, p.713-736, June 1998 [doi>10.1137/S0097539795286119]
	15	Gudmund Skovbjerg Frandsen , Thore Husfeldt , Peter Bro Miltersen , Theis Rauhe , Søren Skyum, Dynamic Algorithms for the Dyck Languages, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.98-108, August 16-18, 1995
	16	Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
	17	Andrew V. Goldberg , Serge A. Plotkin , Gregory E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM Journal on Discrete Mathematics, v.1 n.4, p.434-446, Nov. 1988 [doi>10.1137/0401044]
	18	Ming Gu , Martin Farach , Richard Beigel, An efficient algorithm for dynamic text indexing, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 23-25, 1994, Arlington, Virginia, United States
	19	D. Knuth, J. Morris, and V. Pratt. Fast pattern matching in strings. SIAM Journal on Comp., pages 63-78, 1977.
	20	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	21	J. Meidanis and J. Setubal. Introduction to computational molecular biology. P WS Publiahing Company, a division of international Thomson publishing Inc., first print 1997.
	22	Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer Verlag, Berlin, 1984.
	23	Ku~ Mehlhorn, R. Sundar, and Cl~istian Uhrig. Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica, 17(2):183- 198, 1997.
	24	S. C. Sahinalp , U. Vishkin, Efficient approximate and dynamic matching of patterns using a labeling paradigm, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.320, October 14-16, 1996
	25	Graham A. Stephen, String searching algorithms, World Scientific Publishing Co., Inc., River Edge, NJ, 1994
	26	M. Thorup, Undirected single source shortest paths in linear time, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.12, October 19-22, 1997
	27	Athanasios K. Tsakalidis, Maintaining order in a generalized linked list, Acta Informatica, v.21 n.1, p.101-112, May 1984 [doi>10.1007/BF00289142]
	28	E. Ukkonen. On-line construction of suiFtx trees. Algorithmica, 14(3):249-260, 1995.
	29	M.S. Waterman Introduction to computational biology. Chapman and Hall, Second printing 1996.
	30	P. Weiner. Linear pattern matclfing algorithm. In IEEE Syrup. on Switching and Automata Theory (now FOCS), pages 1-11, 1973.

CITED BY 4

	Pilu Crescenzi , Alberto Del Lungo , Roberto Grossi , Elena Lodi , Linda Pagli , Gianluca Rossi, Text sparsification via local maxima, Theoretical Computer Science, v.304 n.1-3, p.341-364, 28 July 2003
	Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, ACM Transactions on Algorithms (TALG), v.3 n.1, February 2007
	Amihood Amir , Gad M. Landau , Moshe Lewenstein , Dina Sokol, Dynamic text and static pattern matching, ACM Transactions on Algorithms (TALG), v.3 n.2, p.19-es, May 2007
	Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.667-676, January 06-08, 2002, San Francisco, California