Real-time indexing over fixed finite alphabets
Amihood Amir, Igor Nor · Symposium on Discrete Algorithms · 2008
The quest for a real-time indexing algorithm is ove three decades old. To date there is no convincing understandable solution to this problem. This paper provides a real-time indexing algorithm over a constant sized alphabet. Assuming the text is arriving at a constant rate, the algorithm spends O(1) time on every text symbol. Whenever a length m pattern is given, the algorithm decides in time O(m) whether there is an occurrence of the pattern in the text thus far.