Periodicity in Data Streams with Wildcards.

We investigate the problem of detecting periodic trends within a string $S$of length $n$, arriving in the streaming model, containing at most $k$ wildcardcharacters, where $k=o(n)$. A wildcard character is a special character thatcan be assigned any other character. We say $S$ has wildcard-period $p$ ifthere exists an assignment to each of the wildcard characters so that in theresulting stream the length $n-p$ prefix equals the length $n-p$ suffix. Wepresent a two-pass streaming algorithm that computes wildcard-periods of $S$using $\mathcal{O}(k^3\,\mathsf{polylog}\,n)$ bits of space, while we also showthat this problem cannot be solved in sublinear space in one pass. We then givea one-pass randomized streaming algorithm that computes all wildcard-periods$p$ of $S$ with $p<\frac{n}{2}$ and no wildcard characters appearing in thelast $p$ symbols of $S$, using $\mathcal{O}(k^3\mathsf{polylog}\, n)$ space.