Pattern Matching in Dynamic Texts

Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe

In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 819-828, 2000.

Abstract

Pattern matching is the problem of finding all occurrences of a pattern in a text. In a dynamic setting the problem is to support pattern matching in a text which can be manipulated on-line, i.e. the usual situation in text editing.

We present a data structure that supports insertions and deletions of characters and movements of arbitrary large blocks within a text in O(log2 n log log n log*n) time per operation. Furthermore a search for a pattern P in the text is supported in time O(log n loglog n+occ +|P|), where occ is the number of occurrences to be reported. An ingredient in our solution to the above main result is a data structure for the dynamic string equality problem introduced by Mehlhorn, Sundar and Uhrig. As a secondary result we give almost quadratic better time bounds for this problem which in addition to keeping polylogarithmic factors low for our main result also improves the complexity for several other problems.

Copyright notice

Copyright © 2000 by the Association for Computer Machinery, Inc., and the Society for Industrial and Applied Mathematics.

Online version

soda00.pdf (252 Kb)

DOI

doi.acm.org/10.1145/338219.338645

BIBTEX entry

@inproceedings{soda00,
  author = "Stephen Alstrup and Gerth St{\o}lting Brodal and Theis Rauhe",
  booktitle = "Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms",
  doi = "doi.acm.org/10.1145/338219.338645",
  isbn = "0-89871-453-2",
  pages = "819-828",
  title = "Pattern Matching in Dynamic Texts",
  year = "2000"
}

Other versions