Dynamic Pattern Matching

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

Technical Report, DIKU Report 98/27, Department of Computer Science, University of Copenhagen, 16 pages, 1998.

Abstract

Pattern matching is the problem of finding all occurrences of a pattern in a text. For a long period of time significant progress has been made in solving increasingly more generalized and dynamic versions of this problem. In this paper we introduce a fully dynamic generalization of the pattern matching problem. We show how to maintain a family of strings under split and concatenation operations. Given a string in the family, all occurrences of it in the family are reported within time O(log n loglog n+occ) time, where n is the total size of the strings and occ is the number of occurrences. Updates are performed in O(log2 n log log n log*n) time. These bounds are competitive or improve former results for less generalized versions of the problem. As an intermediate result of independent interest, we provide an almost quadratic improvement of the time bounds for the dynamic string equality problem due to Mehlhorn, Sundar and Uhrig.

Online version

diku-98-27.pdf (213 Kb)

BIBTEX entry

@techreport{diku-98-27,
  author = "Stephen Alstrup and Gerth St{\o}lting Brodal and Theis Rauhe",
  institution = "Department of Computer Science, University of Copenhagen",
  number = "DIKU Report 98/27",
  pages = "16",
  title = "Dynamic Pattern Matching",
  year = "1998"
}