Computing The Maximum Exponent in a Stream

We consider the streaming version of the following problem: given an input string s of length n, find the maximum exponent of a substring of s. We prove that any algorithm deciding, w.h.p., whether a string contains a square, uses memory of size $$\varOmega (n)$$ , and thus does not satisfy the limitations of the streaming model. Thus the considered problem has no exact solution in the streaming model. Our main result is a Monte Carlo algorithm which computes the maximum exponent up to an additive error $$\varepsilon <1/2$$ : it outputs a number $$\alpha $$ such that s has a substring of exponent $$\alpha $$ but no substrings of exponent $$\alpha +\varepsilon $$ or higher. The algorithm uses $$\mathcal {O}(\frac{\log ^2 n}{\varepsilon })$$ words of memory and performs $$\mathcal {O}(\log n)$$ operations, including dictionary operations, per input symbol.