Pattern matching in dynamic texts
Stephen Alstrup, Gerth Stølting Brodal, Theis Rauhe · 2000
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(log~nloglognlog*n) time per operation. Furthermore a search for a pattern P in the text is supported in time O(lognloglogn + oct + [PI), 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.