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）之前加到T。任何时候，我们都可以报告O（| P | + k）时间中当前文本中所有出现的模式P，其中| P |是P的长度，k是出现的次数。在恒定大小字母的假设下，这解决了长期存在的开放问题，即存在用于字符串匹配的实时索引方法（请参见[2]）。
展开▼
