In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) expected worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in O(|P| + k) time, where |P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see [2]).
展开▼
机译:在本文中,我们描述了一种数据结构,其在恒定大小的字母表上支持动态到达文本上的模式匹配查询。每个新符号都可以在O(1)预期最坏情况的时间内。在任何时候,我们都可以在O(| p | + k)时间中的当前文本中报告所有出现的模式p,其中p | p的长度是p,k是出现的次数。这在恒定大小的字母表的假设下解决了一个存在于字符串匹配的实时索引方法的长期开放问题(见[2])。
展开▼